Sachverhalt: A. Das Amtsgericht Luzern-Land (heute Bezirksgericht Kriens) verpflichtete A._ und X._ mit Urteil vom 8. November 2007 im Zuge einer paulianischen Anfechtungsklage (gemäss Art. 288 SchKG), den Klägern (Schweizerische Eidgenossenschaft, Kanton Obwalden und Einwohnergemeinde Y._) unter solidarischer Haftbarkeit insgesamt Fr. 1'210'225.50 (zuzüglich 5% Zins seit 30. September 2005) zu bezahlen, "sofern und soweit die Kläger in den gegen B._ hängigen Betreibungen Nrn. 20040743 bis 20040755 und 20041077 des Betreibungsamtes Obwalden oder in einzelnen dieser Betreibungen einen definitiven Verlustschein vorweisen können". Dieses Urteil wurde vom Obergericht des Kantons Luzern am 8. November 2007 (mit Ausnahme des Kostenpunktes) bestätigt. Die von allen Parteien gegen das Obergerichtsurteil gerichteten Beschwerden wies das Bundesgericht mit Urteil vom 26. Mai 2009 ab, soweit es darauf eintrat (BGE 135 III 513). Unter Hinweis auf Pfändungsverlustscheine des Betreibungsamts Obwalden vom 17. Januar 2011 forderte die Finanzverwaltung Obwalden X._ am 1. Februar 2011 auf, die noch ausstehende Forderung im Betrag von Fr. 487'119.-- zu bezahlen. B. Daraufhin gelangte X._ mit Beschwerde vom 10. Februar 2011 an das Obergericht des Kantons Obwalden (als SchKG-Aufsichtsbehörde) und beantragte die Nichtigerklärung der Pfändungsverlustscheine Nrn. 20110031 - 20110044 des Betreibungsamts Obwalden (in den Betreibungen Nrn. 20041077 sowie Nrn. 2004743 - 20040755 des Betreibungsamts Obwalden), eventualiter deren Aufhebung zufolge Gesetzesverletzung. Das Obergericht des Kantons Obwalden wies die Beschwerde mit Urteil vom 16. November 2011 ab, soweit es darauf eintrat. C. Hiergegen gelangt X._ (nachfolgend: Beschwerdeführer) mit Beschwerde in Zivilsachen vom 1. Dezember 2011 an das Bundesgericht. Er verlangt die Aufhebung des vorinstanzlichen Urteils, die Nichtigerklärung der vorgenannten Pfändungsverlustscheine, eventualiter deren Aufhebung zufolge Gesetzesverletzung und subeventualiter die Rückweisung der Sache an die Vorinstanz zu neuer Entscheidung. Das Betreibungsamt Obwalden sowie das Obergericht des Kantons Obwalden haben auf eine Vernehmlassung verzichtet. Die Schweizerische Eidgenossenschaft, der Kanton Obwalden sowie die Einwohnergemeinde Y._ beantragen in ihrer Vernehmlassung die Abweisung der Beschwerde und reichen dem Bundesgericht eine neue Urkunde ein.