Sachverhalt: A. Der in Küsnacht im Kanton Zürich wohnhafte X._ ist Eigentümer der Liegenschaft Nr. xxx in Andermatt. Am 1. Juli 2011 trat dort das von der Offenen Dorfgemeinde Andermatt am 28. Oktober 2010 beschlossene "Reglement über den Tourismus in den Gemeinden Andermatt, Hospental und Realp" (im Folgenden: "Tourismusreglement") in Kraft. Dieses sieht u.a. vor, dass die drei Gemeinden eine "Beherbergungsgebühr" (auch für Zweitwohnungen, Ferienwohnungen und Ferienhäuser) erheben, welche an die Stelle der früheren Kurtaxen tritt. B. Am 31. August 2011 wandte sich X._ an den Gemeinderat Andermatt, äusserte Zweifel an der Anwendbarkeit des neuen Tourismusreglements auf seine Liegenschaft und ersuchte um Erlass einer anfechtbaren (Feststellungs-) Verfügung mit Rechtsmittelbelehrung. Mit Schreiben vom 5. September 2011 stellte der Gemeinderat Andermatt X._ für den Zeitraum vom 1. Juni 2011 bis zum 31. Dezember 2011 eine Beherbergungsgebühr von Fr. 737.80 (zahlbar innert 30 Tagen) provisorisch in Rechnung. Das genannte Schreiben enthielt sodann folgenden Hinweis: "Die definitive Veranlagungsverfügung inklusive der definitiven Rechnung sowie der Rechtsmittelbelehrung werden wir Ihnen zu einem späteren Zeitpunkt zustellen". Hiegegen wandte sich X._ mit einer Verwaltungsbeschwerde an den Regierungsrat des Kantons Uri, wo er die Aufhebung der genannten Rechnung sowie die Aufhebung bzw. Abänderung von Teilen des Tourismusreglements beantragte. Mit Entscheid vom 20. März 2012 wies der Regierungsrat die Beschwerde ab, soweit er darauf eintrat; dies im Wesentlichen mit der Begründung, bei der provisorischen Rechnung vom 5. September 2011 handle es sich nicht um eine Verfügung und damit nicht um ein taugliches Anfechtungsobjekt. Somit entfalle auch eine akzessorische Normenkontrolle. Mit Urteil vom 22. Februar 2013 wies das Obergericht des Kantons Uri (Verwaltungsrechtliche Abteilung) eine von X._ gegen den regierungsrätlichen Entscheid gerichtete Beschwerde ebenfalls ab. C. Mit Eingabe vom 20. März 2013 führt X._ "Beschwerde" beim Bundesgericht mit den Anträgen, das letztgenannte Urteil aufzuheben und das Verfahren an die Vorinstanz zurückzuweisen. Eventuell sei diese anzuweisen, das Verfahren zum Erlass eines Sachentscheides an den Regierungsrat Uri zurückzuweisen. Die Erziehungsdirektion - für den Regierungsrat - sowie das Obergericht verzichten auf Vernehmlassung. Die Einwohnergemeinde Andermatt beantragt, die Beschwerde abzuweisen.