Reichstaller, der auf dem Land aufwuchs, lernte ab dem neunten Lebensjahr Trompete und spielte zunächst in einem kirchlichen Bläserensemble; mit elf Jahren gewann er den Regionalwettbewerb von Jugend musiziert. Dann interessierte er sich für Popmusik und spielte Gitarre. Als ihn ein Onkel mit zu einem Konzert der Jazzwoche Burghausen nahm, war er tief beeindruckt.[1] Er absolvierte zunächst die Berufsfachschule für Musik in Altötting, bevor er von 1980 bis 1984 am Richard-Strauss-Konservatorium München klassische Trompete bei Helmut Reinhart studierte.
Seit Mitte der 1980er Jahre trat Reichstaller mit Benny Bailey und mit Al Porcino auf, die ihn weiter prägten. Nach seinem Wehrdienst arbeitete er weiterhin in der Bigband von Porcino, bei Harald Rüschenbaum, bei Peter Herbolzheimer und mit Rudi Fuesers’ Connexion Latina. Zwischen 1987 und 1989 war er Mitglied von Charly AntolinisJazz Power. Nathan Davis holte ihn 1989 anstelle von Woody Shaw erstmals in seine Paris Reunion Band, mit der er später auch in Japan und im Mittleren Osten auftrat. Gemeinsam mit dem Saxophonisten Axel Kühn gründete er die Gruppe Conception, mit der er mehrere Alben vorlegte. Er arbeitete weiterhin mit John Handy, Klaus Doldinger, Wolfgang Schmid, Max Greger, Paul Kuhn, der WDR Big Band Köln und der hr-Bigband; seit 1997 war er Mitglied der SWR Big Band. Daneben ging er mit seinem eigenen Quartett auf Tournee. Den internationalen Durchbruch schaffte er mit der Paris Reunion Band. Mit dem Sextett von Benny Golson war er 2006 auf Tour. Typisch für sein Trompetenspiel ist „ein hohes Maß an Kontrolle über den Ton, klare Konturen, ein ganz fein abschattierter Klang von prägnanten, kurzen Attacken bis hin zu samtig-geschmackvollen Auszierungen von Phrasen.“[1]
2009 wurde Reichstaller zum Professor für Jazz an der Hochschule für Musik und Theater München ernannt, nachdem das Münchner Richard-Strauss-Konservatorium (wo er bereits seit 1992 als Dozent tätig war) in dieser aufging. Seit 2008 fungierte er dort als Nachfolger von Kurt Maas als Fachbereichsleiter für Jazz.[2] Seit 2010 holt er zudem ans Jazz-Institut der Hochschule amerikanische Jazzgrößen zur mehrtägigen Arbeit mit den besten Studenten.[3]
