Sachverhalt: A. X._ ist Inhaber der Einzelfirma Y._, Sicherheitsdienst, die im Handelsregister des Kantons Uri eingetragen ist. Im Jahre 1999 erhielt er von der Kantonspolizei Zug (heute: Zuger Polizei) die Waffentragbewilligung für Faustfeuerwaffen, die am 4. April 2000 auf halbautomatische Handfeuerwaffen erweitert wurde. Im Dezember 2004 wurde diese Bewilligung bis zum 3. Dezember 2009 verlängert. Am 31. Juli 2006 widerrief die Zuger Polizei die Waffentragbewilligung für Faustfeuerwaffen und halbautomatische Handfeuerwaffen und ersetzte diese durch eine neue Waffentragbewilligung für Faustfeuerwaffen. Mit Entscheid vom 2. Oktober 2006 wies die Zuger Polizei eine dagegen erhobene Einsprache ab. Dagegen führte X._ Beschwerde beim Regierungsrat des Kantons Zug, der die Beschwerde am 16. Januar 2007 abwies. Mit Urteil vom 3. Juni 2008 wies auch das Verwaltungsgericht des Kantons Zug eine bei ihm erhobene Beschwerde ab. B. X._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit dem Antrag, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei ihm die Waffentragbewilligung für Faustfeuerwaffen und halbautomatische Handfeuerwaffen wieder zu erteilen bzw. es sei die Widerrufsverfügung aufzuheben; eventuell sei die Sache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Die Zuger Polizei und die Sicherheitsdirektion des Kantons Zug halten, ohne formell Antrag zu stellen, an ihren Entscheiden fest und verweisen in diesem Sinne auf das Urteil des Verwaltungsgerichts. Dieses schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Polizei hat innert Frist keine Stellungnahme eingereicht.