Sachverhalt: A. Am 17. September 2009 reichte die Y._ AG beim Betreibungsamt Altstätten ein Betreibungsbegehren gegen X._ ein. In der Folge forderte das Betreibungsamt X._ telefonisch zur Abholung des Zahlungsbefehls auf. Am 5. Oktober 2009 erschien X._ auf dem Betreibungsamt und teilte mit, dass er den Zahlungsbefehl nicht entgegennehmen werde. Am 7. Oktober 2009 erhob er Beschwerde mit der Begründung, es liege kein gültiger Betreibungsort vor. Mit Entscheid vom 16. November 2009 wies der Einzelrichter des Kreisgerichts Rheintal als untere Aufsichtsbehörde für das Betreibungswesen die Beschwerde ab. B. Gegen den Entscheid der unteren Aufsichtsbehörde gelangte X._ an das Kantonsgericht St. Gallen als obere kantonale Aufsichtsbehörde für Schuldbetreibung und Konkurs. Die obere kantonale Aufsichtsbehörde trat auf die Beschwerde wegen Fristversäumnis mit Entscheid vom 15. Dezember 2009 nicht ein. C. Mit Eingabe vom 31. Dezember 2009 (Postaufgabe) führt X._ Beschwerde in Zivilsachen. Der Beschwerdeführer beantragt dem Bundesgericht, den Nichteintretensentscheid der oberen kantonalen Aufsichtsbehörde aufzuheben. Weiter ersucht er um aufschiebende Wirkung. Mit Präsidialverfügung vom 4. Februar 2010 wurde der Beschwerde aufschiebende Wirkung zuerkannt. Die obere kantonale Aufsichtsbehörde hat auf eine Stellungnahme verzichtet. Die Y._ AG als Beschwerdegegnerin beantragt das Nichteintreten auf die Beschwerde. Das Betreibungsamt schliesst sinngemäss auf Abweisung der Beschwerde.