Fatti:
A. A._ ha ottenuto l'autorizzazione ad esercitare la professione di fiduciario commercialista il 3 maggio 1988; quella di fiduciario finanziario gli è invece stata rilasciata il 24 agosto 1993.
B. Con decreto d'accusa del 7 dicembre 2004, cresciuto in giudicato, A._ è stato condannato al pagamento di una multa di fr. 4'500.-- per aver commesso il reato di carente diligenza in operazioni finanziarie giusta l'art. 305ter del Codice penale svizzero del 21 dicembre 1937 (CP; RS 311.0).
A seguito di tale condanna, preso atto del fatto che A._ non adempiva più al requisito dell'ottima reputazione e della garanzia di un'attività irreprensibile previsto dall'art. 8 cpv. 1 lett. c e concretizzato dall'art. 8 cpv. 2 lett. b della legge sull'esercizio delle professioni di fiduciario del 18 giugno 1984 (LFid; RL/TI 11.1.4.1), il 19 febbraio 2008 il Consiglio di Stato del Cantone Ticino gli ha revocato le due autorizzazioni citate, intimandogli di conseguenza di cessare immediatamente ogni attività in tal senso. Questa misura è stata confermata su ricorso dal Tribunale cantonale amministrativo con sentenza del 16 giugno 2009.
C. Il 4 settembre 2009, A._ ha inoltrato dinanzi al Tribunale federale un ricorso in materia di diritto pubblico, con cui chiede l'annullamento delle decisioni emesse dalle istanze inferiori.
Con decreto presidenziale del 6 ottobre 2009, al ricorso è stato concesso l'effetto sospensivo.
Chiamato ad esprimersi, il Tribunale cantonale amministrativo si è riconfermato nelle motivazioni e nelle conclusioni della propria sentenza. A nome del Consiglio di Stato, il Dipartimento delle istituzioni del Cantone Ticino ha postulato la reiezione del ricorso.

Diritto:
1. Il Tribunale federale esamina d'ufficio e con piena cognizione la sua competenza (<ref-law>) e l'ammissibilità dei gravami che gli vengono sottoposti (<ref-ruling> consid. 1.1 pag. 3 con rinvii).
1.1 Secondo l'art. 83 lett. t LTF, il ricorso in materia di diritto pubblico è inammissibile contro le decisioni concernenti l'esito di esami e di altre valutazioni della capacità, segnatamente nei settori della scuola, del perfezionamento e dell'esercizio della professione. Nella fattispecie in discussione, le autorità cantonali hanno proceduto alla revoca dell'autorizzazione detenuta dal ricorrente, poiché egli non rispondeva più ai requisiti dell'ottima reputazione e della garanzia di un'attività irreprensibile previsti dall'art. 8 cpv. 1 lett. c e dall'art. 8 cpv. 2 lett. b LFid. Non vertendo la decisione impugnata sulla valutazione delle capacità fisiche o intellettive del ricorrente, l'art. 83 lett. t LTF non trova pertanto applicazione (sentenza 2C_655/2009 del 23 marzo 2010 consid. 1).
1.2 Diretto contro una decisione finale emessa da un tribunale superiore (art. 86 cpv. 2 e art. 90 LTF), il ricorso è stato presentato tempestivamente (art. 46 cpv. 1 lett. b e art. 100 cpv. 1 LTF) dal destinatario della pronuncia contestata. Confermando quest'ultima la revoca a tempo indeterminato dell'autorizzazione detenuta dal ricorrente - ciò che comporta il suo annullamento e la necessità di presentare una nuova domanda al momento in cui i requisiti risultino di nuovo rispettati - dato è anche l'interesse a ricorrere (<ref-law>). L'impugnativa è quindi di massima ammissibile quale ricorso in materia di diritto pubblico.
1.3 Un'eccezione va tuttavia ravvisata nella misura in cui il ricorrente, in accoglimento del gravame, chiede anche l'annullamento dell'originaria decisione del Consiglio di Stato. In virtù dell'effetto devolutivo della procedura di ricorso, tale atto è infatti stato sostituito dalla sentenza del Tribunale cantonale amministrativo. Ne discende che soltanto quest'ultima pronuncia può costituire oggetto d'impugnativa (<ref-ruling> consid. 1.4 pag. 144).
1.4 Con il ricorso in materia di diritto pubblico può in particolare venir censurata la violazione del diritto federale (<ref-law>), nozione che comprende anche i diritti costituzionali dei cittadini (<ref-ruling> consid. 3.1 pag. 447 seg.). Di principio, il Tribunale federale applica comunque il diritto d'ufficio (<ref-law>); esso non è vincolato né agli argomenti fatti valere nel ricorso né ai considerandi sviluppati dall'istanza precedente. La violazione di diritti fondamentali è per contro esaminata unicamente se il ricorrente ha sollevato e motivato tale censura (<ref-law>; <ref-ruling> consid. 2.2 pag. 246; <ref-ruling> consid. 3.2 pag. 88). È necessario che egli specifichi quali diritti ritiene lesi ed esponga le sue critiche in modo chiaro e circostanziato, accompagnandole da un'argomentazione esaustiva; in caso di asserita violazione del divieto d'arbitrio, segnatamente in relazione all'applicazione del diritto cantonale, deve spiegare in che misura la decisione impugnata sia - non solo a livello di motivazione, ma anche di risultato - manifestamente insostenibile, gravemente lesiva di una norma o di un principio giuridico indiscusso, oppure in contraddizione urtante con il sentimento di giustizia ed equità (<ref-ruling> consid. 6 pag. 397; <ref-ruling> consid. 2.1 pag. 9).
2. 2.1 L'art. 1 cpv. 1 LFid prescrive che le attività di fiduciario commercialista, immobiliare e finanziario svolte per conto terzi a titolo professionale nel Cantone Ticino sono soggette ad autorizzazione. Tra i vari requisiti necessari per il suo rilascio - di competenza del Consiglio di Stato - l'art. 8 cpv. 1 lett. c LFid prevede quello dell'ottima reputazione e dell'attività irreprensibile del richiedente. L'art. 8 cpv. 2 lett. b LFid specifica a tal riguardo che non è considerato godere di ottima reputazione rispettivamente garantire un'attività irreprensibile in particolare colui:
"che sia stato condannato in Svizzera, negli ultimi cinque anni, per reati intenzionali o per atti contrari alla dignità professionale a pene detentive o a pene pecuniarie da autorità giudiziarie".
2.2 Secondo l'art. 20 cpv. 1 e 3 LFid, quando l'interessato non adempie più alle condizioni poste dalla legge per il rilascio dell'autorizzazione, il diritto di esercitare la professione viene revocato; venuto a cadere il motivo di revoca, può essere richiesta una nuova autorizzazione.
2.3 Essendo nella fattispecie i presupposti della revoca disciplinati in disposizioni legali specifiche, è quindi sulla base delle stesse che occorre esaminarne la correttezza (<ref-ruling> consid. 7a pag. 314; sentenza 1P.567/2006 del 2 ottobre 2007 consid. 4.2; Annette Guckelberger, Der Widerruf von Verfügungen im schweizerischen Verwaltungsrecht, in ZBl 108/2007 pag. 293 segg., 297).
3. 3.1 La Corte cantonale ha confermato la revoca decisa dal Governo ticinese ritenendo che di fronte al mancato adempimento di una delle condizioni personali previste per il rilascio dell'autorizzazione, l'art. 8 cpv. 2 lett. b LFid non prevede la possibilità di operare alcuna ponderazione degli interessi in gioco, né conferisce all'autorità margine d'apprezzamento. A mente dell'istanza precedente, in base al testo legislativo sarebbe inevitabile che, quando il fiduciario non adempie (più) ai requisiti di legge per essere stato condannato penalmente, egli venga escluso dallo svolgimento di tale attività. In un simile caso, non vi sarebbe inoltre spazio per misure meno incisive, la decisione non essendo di natura disciplinare.
3.2 Nella fattispecie, il ricorrente non contesta né la facoltà da parte del Cantone Ticino di sottoporre ad autorizzazione l'esercizio dell'attività di fiduciario, né il principio di esigere, per poter ottenere tale autorizzazione, l'adempimento di condizioni personali specifiche. Egli non mette neppure altrimenti in discussione la costituzionalità delle norme applicate, aspetto che esula pertanto dalla presente vertenza (sentenze 1C_508/2008 del 22 dicembre 2008 consid. 4.2 e 1P.567/2006 del 2 ottobre 2007 consid. 4.2 con rinvii).
Invocando una violazione dell'art. 27 in relazione con l'<ref-law> e dell'<ref-law>, rimprovera invece all'istanza precedente il non rispetto del principio della proporzionalità nella loro applicazione.
4. 4.1 La libertà economica garantita dall'<ref-law> include in particolare la scelta della professione, il libero accesso a un'attività economica privata e il suo esercizio. Anche chi esercita la professione di fiduciario - nel senso inteso dalla legge qui applicabile - può quindi richiamarsi, in linea di principio, alla citata garanzia costituzionale (proprio con riferimento alla LFid cfr. sentenze 2P.106/2002 del 20 dicembre 2002 consid. 5.2.2 e 2P.89/1990 del 21 dicembre 1990 consid. 2).
4.2 Come tutti i diritti fondamentali, anche la garanzia della libertà economica non è tuttavia assoluta. Essa può essere soggetta a limitazioni, secondo le condizioni previste dall'<ref-law> Ogni restrizione deve cioè fondarsi su una base legale sufficiente, essere giustificata da un interesse pubblico o dalla protezione di diritti fondamentali altrui ed essere proporzionata allo scopo perseguito. La proporzionalità dev'essere data a livello dei contenuti della norma stessa, aspetto qui non in discussione. Nella misura in cui essa conferisca all'autorità un potere di apprezzamento, proporzionale deve però anche essere la sua applicazione in un caso concreto (Pierre Moor, Droit administratif, vol. I, 1994, pag. 417; Paul Richli, Grundriss des schweizerischen Wirtschaftsverfassungsrechts, 2007, pag. 95 segg.)
4.3 Chiamato ad esprimersi in merito, il Tribunale federale esamina liberamente tali aspetti (sentenza 2C_655/2009 del 23 marzo 2010 consid. 4.1 con rinvii). Nella fattispecie, dati i gravi effetti dell'atto impugnato, libero è inoltre pure l'esame dell'interpretazione e dell'applicazione del diritto cantonale ad essi connessa (<ref-ruling> consid. 4.2.2 pag. 157 seg.).
5. Come visto, la contestata revoca è stata pronunciata giusta l'art. 8 cpv. 1 lett. c in relazione con l'art. 8 cpv. 2 lett. b e con l'art. 20 cpv. 1 LFid.
5.1 Mentre l'art. 8 cpv. 1 lett. c LFid si limita a porre tra le condizioni per l'ottenimento dell'autorizzazione all'esercizio dell'attività di fiduciario, l'ottima reputazione e un'attività irreprensibile da parte del candidato - concedendo di principio un certo spazio di manovra alle autorità - l'art. 8 cpv. 2 lett. b, che lo concretizza, non è invece formulato in maniera altrettanto aperta. Secondo questa norma, colui che è stato condannato in Svizzera, negli ultimi cinque anni, per reati intenzionali o per atti contrari alla dignità professionale a pene detentive o a pene pecuniarie da autorità giudiziarie è infatti considerato non godere più di ottima reputazione rispettivamente non garantire più un'attività irreprensibile, a prescindere da ulteriori valutazioni.
5.2 Nella fattispecie, il ricorrente non contesta che la revoca sia stata pronunciata nel termine di cinque anni dalla sua condanna; neppure sostiene che il reato di carente diligenza in operazioni finanziarie di cui all'<ref-law>, in base al quale è stato condannato, non ricada sotto almeno una delle fattispecie indicate nell'art. 8 cpv. 2 lett. b LFid.
Così stando le cose, al ricorrente non giova pertanto argomentare che la fattispecie penale andasse contestualizzata e denunciare che la decisione del Consiglio di Stato - cui non sono state accompagnate misure provvisionali specifiche - e il giudizio del Tribunale cantonale amministrativo non abbiano tenuto conto delle particolarità del caso concreto e delle conseguenze che una revoca comporta. In presenza di una simile condanna, in base all'art. 8 cpv. 2 lett. b, cui rinvia l'art. 20 cpv. 1 LFid, all'autorità competente non restava infatti altro che constatare che uno dei requisiti cui deve adempiere il detentore di un'autorizzazione risultava essere venuto meno, e ordinare la revoca della stessa (in questo senso, cfr. anche messaggio del Consiglio di Stato n. 2697 dell'8 marzo 1983 concernente la LFid, commento ad art. 16 e 17, in cui viene indicato che il difetto di uno solo dei requisiti basta a giustificare la revoca).
Un esame più sfumato della fattispecie avrebbe in effetti presupposto una libertà nell'applicazione, che l'art. 8 cpv. 2 lett. b non accorda (PIERRE MOOR, Principes de l'activité étatique et responsabilité de l'État, in Droit Constitutionnel suisse, 2000, pag. 265 segg. n. 60; GAAC 69/2005 n. 21 consid. 5.1).
5.3 Contrariamente a quanto sostenuto dal ricorrente, neppure può essere detto che il provvedimento preso sia troppo severo. Anche se può venir comprensibilmente percepita come tale a livello soggettivo, la revoca decisa dal Consiglio di Stato dell'autorizzazione in oggetto - che ha carattere di permesso di polizia (sentenza 2P.257/1994 del 4 dicembre 1995 consid. 1b) -, non ha infatti natura disciplinare e neppure dipende dalla pronuncia parallela di una simile sanzione da parte del competente Consiglio di vigilanza giusta l'art. 16 segg. LFid, bensì solo dal sussistere o meno dei requisiti richiesti per il rilascio (Tschannen/Zimmerli/Müller, Allgemeines Verwaltungsrecht, 3. ed. 2009, pag. 314 n. 44).
In questo senso, proprio perché il procedimento non aveva carattere disciplinare, la Corte cantonale ha quindi pure correttamente rilevato come, in difetto di uno dei chiari requisiti richiesti, il Consiglio di Stato - che non si è comunque opposto a che il gravame godesse dell'effetto sospensivo, nemmeno in questa sede - non avesse affatto spazio per la pronuncia di misure meno incisive e dovesse revocare il permesso a suo tempo concesso (sentenze 2P.274/2004 del 13 aprile 2005 consid. 3.2 e 2P.309/2005 del 17 maggio 2006 consid. 3.3.1, casi dove però l'autorità disponeva di una certa libertà e quindi vi era pure la possibilità di procedere a una verifica della proporzionalità nella fattispecie concreta).
5.4 Altrettanto irrilevante è infine che, nel decreto d'accusa emesso a carico del ricorrente, il Procuratore pubblico non abbia ipotizzato l'applicazione della misura accessoria dell'interdizione dell'esercizio della professione giusta l'art. 54 vCP. Oltre alla protezione della sicurezza e dell'ordine pubblici, le autorità penali perseguono infatti anche altri scopi, segnatamente di carattere preventivo e - in analogia a quanto vale per l'ambito disciplinare - repressivo che la misura della revoca prevista dalla LFid invece non ha (cfr. sentenza 2P.274/2004 del 13 aprile 2005 consid. 5.4). Nei due contesti, si giustifica pertanto l'applicazione di parametri differenti.
5.5 Per quanto precede, non adempiendo il ricorrente più alle condizioni personali previste, la revoca dell'autorizzazione in concreto ordinata non può essere considerata in contrasto con la garanzia della libertà economica rispettivamente con il principio di proporzionalità, nel senso da lui denunciato (cfr. analogamente sentenza 2P.159/2005 del 30 giugno 2006 consid. 3.3).
6. Al ricorrente non giova nemmeno il richiamo all'<ref-law>, quale norma che prescrive il rispetto del principio della proporzionalità da parte delle autorità in ogni loro ambito di attività.
In effetti, laddove il principio della proporzionalità in esso ancorato non è posto in relazione con uno specifico diritto costituzionale, la censura della sua violazione si confonde in sostanza con quella dell'arbitrio (<ref-ruling> consid. 4; Tschannen/Zimmerli/Müller, op. cit., pag. 159 seg. n. 20 segg.). Conseguentemente, è necessario che chi vi si appella spieghi con una motivazione conforme agli art. 42 cpv. 2 e 106 cpv. 2 LTF per quali ragioni la decisione impugnata sarebbe non solo discutibile, ma addirittura insostenibile (cfr. precedente consid. 1.4).
Una simile motivazione, che costituisce requisito di ammissibilità, manca però nella fattispecie. In ogni caso, dato che neppure il ricorrente contesta che la decisione di revoca poggi sulla constatazione dell'assenza di un requisito esplicitamente previsto dall'art. 8 cpv. 2 lett. b LFid, non può certo venir rimproverato al Tribunale cantonale amministrativo di essere incorso nell'arbitrio nell'aver constatato, in applicazione di tale norma - di cui non è in discussione un controllo accessorio -, che egli non rispondesse più a tutti i requisiti in essa indicati (cfr. analogamente sentenza 1C_508/2008 del 22 dicembre 2008 consid. 4.2).
7. 7.1 Nella misura in cui è ammissibile, il ricorso va pertanto respinto poiché infondato. Per quanto severa, la misura di revoca dev'essere confermata.
7.2 Pendente causa, il termine di 5 anni previsto dall'art. 8 cpv. 2 lett. b LFid è nel frattempo trascorso. Come già rilevato da questa Corte (sentenza 2P.149/1999 del 20 dicembre 1999 consid. 3b.dd), la condanna inflitta al ricorrente il 7 dicembre 2004 non costituisce quindi più un ostacolo all'adempimento del requisito richiesto dall'art. 8 cpv. 2 lett. b LFid. Di conseguenza, egli potrà sin d'ora richiedere nuovamente il rilascio di un'autorizzazione secondo quanto previsto dall'art. 20 cpv. 3 LFid.
8. Le spese giudiziarie seguono la soccombenza (<ref-law>). Non si assegnano ripetibili ad autorità vincenti (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 2'500.-- sono poste a carico del ricorrente.
3. Comunicazione al patrocinatore del ricorrente, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.