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.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Endentscheid einer oberen kantonalen Gerichtsbehörde (vgl. Art. 86 Abs. 1 lit. d in Verbindung mit <ref-law>), der eine Angelegenheit des öffentlichen Rechts betrifft und deshalb der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (<ref-law>). Weil zudem keiner der Ausschlussgründe gemäss <ref-law> erfüllt ist und dem Beschwerdeführer nach <ref-law> die Rechtsmittellegitimation zukommt, ist grundsätzlich auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten einzutreten.
1.2 Unzulässig ist der Antrag des Beschwerdeführers, die erstinstanzliche Widerrufsverfügung sei aufzuheben. Diese ist durch die Rechtsmittelentscheide bzw. zuletzt durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mitangefochten (<ref-ruling> E. 1.4 S. 144; <ref-ruling> E. 1 S. 441). Insoweit ist auf die Beschwerde nicht einzutreten.
1.3 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Vorliegend ist insbesondere der Beschwerdegrund der Verletzung von Bundesrecht, unter Einschluss des Bundesverfassungsrechts, gemäss <ref-law> von Interesse. Das Bundesgericht wendet dabei das Recht von Amtes wegen an (<ref-law>). Nach <ref-law> hat freilich die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid das massgebliche Recht verletzt (<ref-law>). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich die Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzen (<ref-ruling>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254).
2. 2.1 Das Bundesgesetz vom 20. Juni 1997 über Waffen, Waffenzubehör und Munition (Waffengesetz, WG; SR 514.54) bezweckt die Bekämpfung des Waffenmissbrauchs (vgl. <ref-law>). Nach <ref-law> ist das Recht auf Waffenerwerb, -besitz und -tragen im Rahmen des Waffengesetzes gewährleistet. Insbesondere benötigt gemäss <ref-law> eine Waffentragbewilligung, wer in der Öffentlichkeit eine Waffe tragen will. Eine solche erhält nach <ref-law>, wer (gemäss <ref-law>) die Voraussetzungen für die Erteilung des Waffenerwerbsscheins erfüllt (lit. a), glaubhaft macht, dass die Waffe benötigt wird, um sich selbst, andere Personen oder Sachen vor einer tatsächlichen Gefährdung zu schützen (lit. b), und eine Prüfung über die Handhabung von Waffen und über die Kenntnis der rechtlichen Voraussetzungen des Waffengebrauchs bestanden hat (lit. c). Die Bewilligung wird von der zuständigen Behörde des Wohnsitzkantones für eine bestimmte Waffenart und für längstens fünf Jahre erteilt (Art. 27 Abs. 3 erster Satz WG). Nach Art. 29 Abs. 2 der Verordnung vom 21. September 1998 über Waffen, Waffenzubehör und Munition (WV; SR 514.541) prüft die Behörde, ob die Voraussetzungen, insbesondere der Bedürfnisnachweis, erfüllt sind.
2.2 Gemäss § 2 der zugerischen Verordnung vom 15. Dezember 1998 zur Bundesgesetzgebung über Waffen, Waffenzubehör und Munition (WV ZG) vollzieht die Zuger Polizei die Bestimmungen des Waffenrechts. Sie ist auch zuständig für die Erteilung der Waffentragbewilligung (<ref-law> ZG). Nach <ref-law> ZG kann das Bedürfnis, eine Waffe zu tragen, namentlich bei Personen vorliegen, die aufgrund ihrer beruflichen Stellung einer tatsächlichen Gefährdung ausgesetzt sind.
2.3 Bei der Waffentragbewilligung handelt es sich um eine Dauerbewilligung im Sinne einer Polizeierlaubnis, mit der festgestellt wird, dass dem Tragen einer Waffe der darin vorgesehenen Art während der Bewilligungsdauer keine Hindernisse entgegenstehen. Nach der bundesgerichtlichen Rechtsprechung setzt eine Waffentragbewilligung eine tatsächliche Gefährdung voraus. Diese braucht nicht konkret zu sein; es genügt, wenn für den Gesuchsteller aufgrund seiner Aufgabe oder Funktion, seiner Lebensbedingungen oder aufgrund anderer besonderer Umstände ein spezielles Risiko bzw. eine erhöhte Wahrscheinlichkeit für eine Gefahrensituation besteht. Das Tragen der Waffe muss freilich zum Schutz des Gesuchstellers oder zum Schutz von Dritten geboten erscheinen; es ist nur gerechtfertigt, wenn der Gefahr eines Angriffs nicht auf andere zumutbare Weise begegnet werden kann (Urteile des Bundesgerichts 2A.411/2000 vom 22. März 2001 E. 2b; 2A.26/2001 vom 1. Mai 2001 E. 3a in: ZBl 103/2002 S. 220; 2A.203/2002 vom 29. August 2002 E. 2.4).
2.4 Es ist unbestritten, dass der Beschwerdeführer als im Sicherheitsdienst tätige Person zu denjenigen Personen zählt, deren Bedürfnis zum Tragen einer Waffe grundsätzlich ausgewiesen ist. Er verfügt denn auch weiterhin über die Tragbewilligung für Faustfeuerwaffen. Die Vorinstanz leitet aber aus der gesetzlichen Beschränkung einer Waffentragbewilligung für eine bestimmte Waffenart in Verbindung mit dem Gebot der Geeignetheit und Notwendigkeit des Waffentragens mit Blick auf die Abwehr eines potentiellen Angriffs ab, dass nicht jede Art von Waffen mitgeführt werden dürfe. Vielmehr sei nur das Tragen solcher Waffen zulässig, die zum Zwecke der Abwehr der tatsächlichen Gefährdung geeignet seien. Diese Gesetzesauslegung ist nicht zu beanstanden. Der vom Gesetz verfolgte Zweck der Missbrauchsbekämpfung steht in engem Zusammenhang zur Wahrung der öffentlichen Sicherheit. Er rechtfertigt die Beschränkung der Tragbewilligung auf Waffenarten, die der Bekämpfung der jeweils potentiellen Gefahr am besten entsprechen. Dabei ist nicht von der theoretisch grössten Gefährdung auszugehen, denn ein solcher Ansatz wäre von vornherein uferlos und würde dem Ziel der Missbrauchsbekämpfung zuwiderlaufen, sondern es ist auf die wahrscheinliche Gefahr abzustellen. Daraus ergibt sich auch die geeignete Abwehrmassnahme bzw. die Waffenart, deren Tragen zu bewilligen ist.
2.5 Der Bund führt die Zentralstelle Waffen (ZSW), unter deren Leitung als polizeiliches Fachgremium der Arbeitsausschuss Waffen und Munition (AWM) steht. Dieser wirkt unter anderem bei der Entwicklung und beim Vollzug der Waffengesetzgebung mit, berät die Vollzugsorgane des Bundes und der Kantone und erlässt Richtlinien (vgl. <ref-law> und <ref-law>). In der Empfehlung Nr. 22 des Arbeitsausschusses wurde den Vollzugsbehörden die Auffassung der Zentralstelle und des Ausschusses mitgeteilt, dass Waffentragbewilligungen an Sicherheitsfirmen lediglich für Faustfeuerwaffen oder Pump Actionflinten (für spezielle Einsätze) erteilt werden sollten. Die Empfehlung richtet sich an die Vollzugsbehörden und ist als interne Richtlinie für die Gerichte nicht verbindlich. Soweit sie aber eine überzeugende Konkretisierung der rechtlichen Vorgaben enthält, ist davon nur bei Vorliegen triftiger Gründe abzuweichen (vgl. <ref-ruling> E. 5.1.2 S. 203 f. mit Hinweisen). Solche sind hier nicht ersichtlich; im Gegenteil überzeugt die in der Empfehlung vorgeschlagene Gesetzesauslegung. Entgegen den vom Beschwerdeführer beanstandeten und insofern möglicherweise leicht irreführenden Erwägungen der Vorinstanz und der Fachgremien des Bundes kommt es dabei nicht so sehr auf die Unterscheidung von Offensiv- und Defensivwaffen an. Denn wie der Beschwerdeführer nicht ganz zu Unrecht einwendet, können auch Defensivwaffen offensiv eingesetzt werden und umgekehrt. Entscheidend ist vielmehr, dass aus heutiger Sicht für die überwiegend wahrscheinlichen Notwehrsituationen, wie sie im Personen- und Wertsachenschutz eintreten, der Einsatz von Faustfeuerwaffen genügt und solche für entsprechende Tätigkeiten daher als geeignet erscheinen. Halbautomatische Handfeuerwaffen führen demgegenüber zu einer überhöhten Bewaffnung, die dem normalen tatsächlichen Risikopotential nicht entspricht. Dabei bleibt es jedem Gesuchsteller vorbehalten, eine ausnahmsweise erhöhte Gefährdung glaubhaft zu machen. Das ist dem Beschwerdeführer aber nicht gelungen und wird von ihm an sich auch gar nicht behauptet, weshalb der angefochtene Entscheid insoweit nicht gegen Bundesrecht verstösst.
2.6 Soweit sich der Beschwerdeführer in diesem Zusammenhang auf Grundrechte beruft, genügt die Beschwerdeschrift den Anforderungen an eine rechtsgenügliche Begründung nicht, weshalb insofern auf die Beschwerde nicht eingetreten werden kann (vgl. E. 1.3). Im Übrigen wären für allfällige Grundrechtseingriffe ohnehin die entsprechenden Voraussetzungen von <ref-law> (gegebenenfalls in Verbindung mit <ref-law>) erfüllt.
3. 3.1 Im vorliegenden Fall geht es nicht um die Gewährung einer Bewilligung, sondern um den am 31. Juli 2006 erfolgten Widerruf der dem Beschwerdeführer im Jahre 1999 erteilten und am 3. Dezember 2004 verlängerten Waffentragbewilligung für halbautomatische Handfeuerwaffen. Der Beschwerdeführer trägt insofern eine Begründung vor, aus der sich nur bedingt ergibt, weshalb der angefochtene Entscheid mit Blick auf den Widerruf der Bewilligung Bundesrecht verletzen sollte. Namentlich legt er nicht dar, weshalb die Vorinstanz in verfassungswidriger Weise gegen das einschlägige kantonale Verfahrensrecht verstossen haben sollte. Er beruft sich einzig auf die von der Lehre anerkannten allgemeinen Grundsätze für den Widerruf von Verfügungen. Ob es sich dabei um eine taugliche Rüge handelt (vgl. E. 1.3), erscheint fraglich, kann aber offen bleiben. Selbst wenn darauf einzutreten wäre, erwiese sich die Rüge als unbegründet.
3.2 Auf kantonaler Ebene sieht § 29 des Gesetzes vom 1. April 1976 über den Rechtsschutz in Verwaltungssachen des Kantons Zug (Verwaltungsrechtspflegegesetz; VRG) vor, dass die Verwaltungsbehörde ihre Entscheide aus wichtigen Gründen ausserhalb eines Revisionsverfahrens von Amtes wegen oder auf Gesuch hin ändern oder aufheben kann, soweit nicht besondere Vorschriften, der Grundsatz von Treu und Glauben oder andere allgemein anerkannte Rechtsgrundsätze dies ausschliessen oder einschränken.
3.3 Nach der bundesgerichtlichen Rechtsprechung können Verwaltungsakte, die wegen wesentlicher Änderung der tatsächlichen oder rechtlichen Verhältnisse dem Gesetz nicht oder nicht mehr entsprechen, grundsätzlich widerrufen werden. Der Widerruf ist allerdings nur zulässig, wenn eine allgemeine Interessen- bzw. Wertabwägung ergibt, dass das Interesse an der richtigen Durchsetzung des objektiven Rechts dasjenige an der Wahrung der Rechtssicherheit bzw. am Vertrauensschutz überwiegt. Dem Postulat der Rechtssicherheit kommt in der Regel dann der Vorrang zu, wenn durch die frühere Verfügung ein subjektives Recht begründet worden oder die Verfügung in einem Verfahren ergangen ist, in welchem die sich gegenüberstehenden Interessen allseitig zu prüfen und gegeneinander abzuwägen waren, oder wenn der Private von einer ihm durch die fragliche Verfügung eingeräumten Befugnis bereits Gebrauch gemacht hat. Diese Regel gilt allerdings nicht absolut; ein Widerruf kann auch in einem der drei genannten Fälle in Frage kommen, wenn er durch ein besonders gewichtiges öffentliches Interesse geboten ist und wenn nicht bereits nicht mehr rückgängig zu machende Folgen eingetreten sind (vgl. <ref-ruling> E. 1a/aa S. 276; <ref-ruling> E. 4c S. 310; Ulrich Häfelin/Georg Müller/Felix Uhlmann, Allgemeines Verwaltungsrecht, 5. Aufl., Zürich 2006, S. 206 ff. Rz. 990 ff.). Einzubeziehen sind alle Aspekte des Einzelfalls. Für den Ausgang der Güterabwägung kann insbesondere eine Rolle spielen, wie lange ein gesetzwidriger Zustand schon dauert oder noch andauern würde (Urteil des Bundesgerichts 1C_43/2007 vom 9. April 2008 E. 5.3 nicht publ. in: <ref-ruling>). Besteht die Änderung in einer neuen Verwaltungspraxis, darf die Verfügung über ein Dauerrechtsverhältnis nur ausnahmsweise angepasst werden, was insbesondere dann zulässig ist, wenn die neue Praxis derart allgemeine Verbreitung gefunden hat, dass deren Nichtbefolgung als Verstoss gegen das Gleichheitsgebot erschiene (Häfelin/Müller/Uhlmann, a.a.O., Rz. 999; <ref-ruling> E. 4a S. 161 f.).
3.4 Vorliegend überwiegt das öffentliche Interesse an der richtigen Anwendung des objektiven Rechts das private Interesse des Beschwerdeführers an der Rechtssicherheit. Die Wahrung der öffentlichen Sicherheit, die im Anschluss an diverse Ereignisse durch die Empfehlung Nr. 22 des Arbeitsausschusses Waffen und Munition neu eingeschätzt wurde, erscheint besonders bedeutsam und ist deutlich höher zu gewichten als der Schutz des Vertrauens des Beschwerdeführers, weiterhin gemäss der erteilten Bewilligung eine halbautomatische Handfeuerwaffe tragen zu dürfen. Ein weiteres Ziel der fraglichen Empfehlung Nr. 22, abgesehen von demjenigen der Missbrauchsbekämpfung, war die Begründung einer einheitlichen gesamtschweizerischen Praxis. Offenbar werden solche Waffen in der Schweiz denn auch für private Sicherheitsunternehmen seit Jahren nicht mehr bewilligt. Warum beim Beschwerdeführer eine Ausnahme zu machen wäre, legt er, wie bereits erwähnt (vgl. E. 2.5), nicht dar, weshalb die Nichtanwendung der neuen Praxis auf den Beschwerdeführer mit Blick auf das Rechtsgleichheitsgebot bedenklich erschiene. Die widerrufene Bewilligung zeitigte auch keine nicht rückgängig zu machenden Wirkungen: Weder ergeben sich solche aus dem bereits erfolgten Gebrauch, noch löste die Bewilligung erhebliche irreversible Investitionen aus. Es kann sich mithin einzig fragen, ob der Widerruf einer Bewilligung, die Ende 2009 ohnehin ausläuft, in zeitlicher Hinsicht zwingend war. Erstinstanzlich erging der Widerrufsentscheid allerdings bereits im Sommer 2006 und damit dreieinhalb Jahre vor Ablauf der Bewilligung. Auch in dieser Hinsicht erweist sich der Widerruf mithin als verhältnismässig. Schliesslich kann der Beschwerdeführer aus dem Umstand, dass ihm kurz vor dem Widerruf eine Waffenerwerbsbewilligung für eine halbautomatische Handfeuerwaffe erteilt worden ist, nichts zu seinen Gunsten ableiten, unterscheiden sich doch die Voraussetzungen für den Erwerb deutlich von denjenigen für das Tragen einer Waffe (vgl. Art. 8 und 27 WG). Insbesondere bedarf es für den Waffenerwerb weder eines Bedürfnisnachweises noch einer Prüfung über die Handhabung der Waffe und über die Kenntnisse der rechtlichen Voraussetzungen des Waffengebrauches. Der angefochtene Entscheid erfüllt demnach die bundesrechtlichen Anforderungen an den Widerruf einer Verfügung.
4. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang wird der Beschwerdeführer kostenpflichtig (Art. 65 und 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Zuger Polizei sowie der Sicherheitsdirektion und dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, und dem Eidgenössischen Justiz- und Polizeidepartement, Bundesamt für Polizei, schriftlich mitgeteilt.
Lausanne, 26. Januar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Merkli Uebersax