Fatti:
A. A._ ha ottenuto l'autorizzazione ad esercitare la professione di fiduciario commercialista il 25 marzo 1998; quella di fiduciario finanziario gli è invece stata rilasciata il 7 novembre 2000.
Con decreto d'accusa del 1° settembre 2008, cresciuto in giudicato, egli è stato condannato ad una pena pecuniaria di fr. 2'400.-- (trenta aliquote di fr. 80.-- ciascuna), sospesa con un periodo di prova di tre anni, nonché a una multa di fr. 800.--, per aver commesso il reato di conseguimento fraudolento di una falsa attestazione giusta l'art. 253 del Codice penale svizzero del 21 dicembre 1937 (CP; RS 311.0), inducendo un notaio ad attestare in un documento pubblico un fatto di importanza giuridica contrario alla verità.
B. Preso atto di tale condanna, quindi di come A._ non adempisse più al requisito dell'ottima reputazione e della garanzia di un'attività irreprensibile giusta l'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), con decisione del 2 settembre 2009 il Consiglio di Stato del Cantone Ticino gli ha revocato le due autorizzazioni citate.
Questa misura, adottata dopo aver annullato una prima procedura in cui era stata per errore prospettata solo la revoca dell'autorizzazione all'esercizio della professione di fiduciario commercialista ed averne aperta una seconda concernente entrambi i permessi in possesso di A._, è stata confermata dal Tribunale amministrativo del Cantone Ticino con sentenza del 12 agosto 2010.
C. Con ricorso in materia di diritto pubblico del 17 settembre 2010, A._ ha impugnato tale giudizio davanti al Tribunale federale, chiedendone l'annullamento.
In via preliminare, egli denuncia una violazione del diritto di essere sentito ed ulteriori lacune procedurali che, a suo modo di vedere, avrebbero dovuto portare la Corte cantonale a dichiarare nulla rispettivamente ad annullare la decisione del Consiglio di Stato. Con esplicito richiamo alla garanzia della libertà economica ancorata nell'<ref-law> ed alla facoltà di una sua limitazione unicamente in base alle condizioni previste dall'<ref-law>, il ricorrente censura quindi il fatto che l'art. 8 cpv. 2 lett. b e l'art. 20 cpv. 1 LFid, su cui basa la revoca, non permettano nessuna ponderazione degli interessi in gioco.
Con decreto presidenziale del 14 ottobre 2010 è stato concesso l'effetto sospensivo al gravame.
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.
Ottenuta la facoltà di replicare, con atto del 23 novembre 2010 il ricorrente ha in sostanza ribadito le argomentazioni presentate con l'impugnativa. Interpellato in merito, il Tribunale cantonale amministrativo ha rinunciato a formulare ulteriori osservazioni. Da parte sua, il Consiglio di Stato ha chiesto nuovamente il rigetto 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. 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_536/2009 del 21 giugno 2010 consid. 1.1).
1.2 Diretto contro una decisione finale di un tribunale superiore (art. 86 cpv. 2 e art. 90 LTF), il ricorso è stato presentato tempestivamente (<ref-law>) dal destinatario della pronuncia contestata. Confermando quest'ultima la revoca dell'autorizzazione da lui detenuta, dato è anche l'interesse a ricorrere (<ref-law>). L'impugnativa è quindi ammissibile quale ricorso in materia di diritto pubblico.
1.3 Ammissibile è segnatamente pure la censura volta ad un controllo accessorio dei disposti su cui poggia la revoca (precedente consid. C). Per mezzo dell'impugnazione di un atto concreto davanti al Tribunale federale può in effetti essere fatta valere anche l'incostituzionalità della norma applicata (<ref-ruling> consid. 5.6 pag. 5). Va tuttavia precisato che, chiamato ad esprimersi in un simile contesto, iI Tribunale federale non esamina la conformità alla Costituzione con riguardo a tutte le fattispecie possibili, bensì unicamente nell'ottica del caso specifico e, qualora la critica si dimostrasse fondata, annulla solamente I'atto concreto, non invece la norma litigiosa sulla quale esso si basa (<ref-ruling> consid. 4 pag. 54; <ref-ruling> consid. 3.1 pag. 274 e rinvii).
2. 2.1 Con il ricorso in materia di diritto pubblico può in particolare venir censurata la violazione del diritto federale (<ref-law>), nozione che comprende 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, inclusi quelli ancorati direttamente nel diritto internazionale, è invece esaminata unicamente se il ricorrente ha sollevato e motivato tale censura (<ref-law>; <ref-ruling> consid. 2.2 pag. 246; sentenza 2C_221/2009 del 21 gennaio 2010 consid. 1.3). Nella sua impugnativa, è necessario che egli specifichi quali diritti ritiene lesi ed esponga le 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 Nella fattispecie, il gravame rispetta solo in parte questi requisiti. In relazione al suo diritto di essere sentito, il ricorrente denuncia la violazione dell'art. 6 cifra 3 CEDU in modo generico, soffermandosi nel seguito esclusivamente sull'<ref-law>
Sempre in relazione al suo diritto di essere sentito, ma anche a sostegno della tesi secondo cui la decisione del Consiglio di Stato dovesse essere dichiarata nulla rispettivamente andasse annullata a causa di ulteriori lacune procedurali, censura inoltre la semplice violazione degli art. 18-20 della legge cantonale di procedura per le cause amministrative del 19 aprile 1966 (LPamm; RL/TI 3.3.1.1; ricorso p.to 3, pag. 13) e degli art. 18 e 20 LFid che, come tale, non può costituire motivo di ricorso.
Con riferimento a queste specifiche critiche, l'impugnativa dev'essere pertanto dichiarata inammissibile.
3. 3.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 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 precisa al 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".
3.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; competente per decretare la revoca è il Consiglio di Stato, il quale si pronuncia su preavviso del Consiglio di vigilanza sull'attività dei fiduciari.
3.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).
4. In via preliminare, il ricorrente rimprovera al Tribunale cantonale amministrativo di non avere sanzionato, considerandola sanata, una violazione del suo diritto di essere sentito da parte del Consiglio di Stato, per aver deciso la revoca delle autorizzazioni in discussione senza preventivamente trasmettergli, permettendogli di prendere posizione al riguardo, il preavviso raccolto dal Consiglio di vigilanza.
4.1 Dal diritto di essere sentito ancorato nell'<ref-law> - quale garanzia minima che può essere concretizzata in norme di diritto cantonale, che però il ricorrente omette di invocare o non richiama nelle dovute forme (precedente consid. 2.2) - viene effettivamente dedotto il diritto di partecipare all'assunzione delle prove, di prenderne conoscenza e di determinarsi al riguardo (<ref-ruling> consid. 2.2 seg. con rinvii). Essendo di natura formale, la mancata concessione di tale diritto comporta di principio l'annullamento della decisione impugnata, indipendentemente dalle conclusioni che occorre trarre nel merito (<ref-ruling> consid. 5.1 pag. 390; <ref-ruling> consid. 3d/aa pag. 437).
4.2 Il Tribunale federale ammette ciò nondimeno che, a determinate condizioni, una lesione dei diritti dedotti dall'<ref-law> possa anche essere sanata.
Così è quando l'autorità di ricorso adita dispone dello stesso potere di esame dell'autorità cui viene imputata la lesione del diritto di essere sentiti, la violazione in discussione non è grave e la sanatoria non comporta un pregiudizio per il ricorrente (<ref-ruling> consid. 2.6.1 pag. 285 con rinvii).
4.3 Senza che occorra esprimersi definitivamente in merito alla lesione denunciata, verificando tra l'altro se - in considerazione del fatto che l'assunzione del preavviso dell'autorità di vigilanza è espressamente prevista dall'art. 20 cpv. 1 LFid - il ricorrente non dovesse informarsi motu proprio sulla sua acquisizione agli atti e sui suoi contenuti (<ref-ruling> consid. 4a pag. 303 seg.), le condizioni per una sua eventuale riparazione devono essere riconosciute anche nella fattispecie.
4.3.1 Il necessario potere cognitivo del Tribunale cantonale amministrativo è in effetti dato. Il ricorrente, che ha interposto ricorso contro la decisione del Consiglio di Stato dopo aver ottenuto dalla Divisione della giustizia l'incarto completo, comprensivo del preavviso in parola, non contesta da parte sua tale potere né mette in discussione il fatto che la Corte cantonale ne faccia pienamente uso (<ref-ruling> consid. 2.6.4. pag. 286 e contrario).
4.3.2 Considerato che il ricorrente stesso relativizza fortemente l'importanza dell'atto omesso affermando che, visto il tenore dell'art. 8 cpv. 2 lett. b LFid, la pronuncia di una revoca nei suoi confronti era comunque inevitabile (ricorso p.to 4, pag. 19), neppure può essere concluso che la natura dell'eventuale lesione ne escluda a priori la riparazione in una fase successiva. Se è infatti vero che un vizio di natura formale va di principio esaminato prescindendo da valutazioni di merito, è altrettanto vero che un giudizio sulla rilevanza dell'atto omesso viene in casu formulato direttamente da chi censura la violazione del suo diritto di essere sentito e non può quindi essere ignorato (Michele Albertini, Der verfassungsmässige Anspruch auf rechtliches Gehör im verwaltungsverfahren des modernen Staates, 2000, pag. 457 seg. con rinvii alla giurisprudenza).
4.3.3 In mancanza di ulteriori elementi in tal senso, il pieno potere d'esame esercitato in materia dalla Corte cantonale - unitamente all'effetto sospensivo di cui gode un ricorso davanti ad essa depositato quando, come nella fattispecie, tale effetto non è stato ritirato dall'istanza precedente (art. 47 LPamm) - permette infine anche di escludere che la riparazione di un'eventuale lesione commessa dal Consiglio di Stato abbia comportato dei reali pregiudizi per il ricorrente.
4.4 Per quanto precede, ritenendo sanata la violazione denunciata, la Corte cantonale non ha affatto violato il suo diritto di essere sentito.
5. Nel merito, con esplicito richiamo alla garanzia della libertà economica ancorata nell'<ref-law>, il ricorrente denuncia in sostanza come, davanti al mancato adempimento di una delle condizioni richieste per l'esercizio della professione, l'art. 8 cpv. 2 lett. b e l'art. 20 cpv. 1 LFid non permettano nessuna ponderazione degli interessi in gioco, prevedendo semplicemente la revoca dell'autorizzazione per un periodo di cinque anni, e comportino nella fattispecie una lesione del principio della proporzionalità (art. 5 cpv. 2 e <ref-law>).
Egli si lamenta del fatto che la Corte cantonale abbia lasciato aperta la questione sollevata - a suo dire, basandosi a torto solo sulla natura di permesso di polizia dell'autorizzazione rilasciata -, e ripresenta quindi la stessa censura anche in questa sede, postulando un controllo accessorio delle norme in discussione.
5.1 Al pari degli altri diritti fondamentali, la garanzia della libertà economica - che tutela anche il libero accesso ad un'attività economica privata e il suo esercizio (sentenza 2C_536/2009 del 21 giugno 2010 consid. 4.1 con rinvii) - non è assoluta. Essa può essere soggetta a limitazioni, secondo le condizioni previste dall'art. 36 cpv. 1-3 Cost. Ogni restrizione deve pertanto fondarsi su una base legale sufficiente (cpv. 1), essere giustificata da un interesse pubblico (cpv. 2) ed essere proporzionata (cpv. 3), ovvero risultare idonea e necessaria per realizzare lo scopo perseguito e comportare effetti ragionevolmente sopportabili in considerazione dell'interesse pubblico tutelato (<ref-ruling> consid. 5.2 pag. 438 seg.; <ref-ruling> consid. 5.1 pag. 297 seg.; <ref-ruling> consid. 3 pag. 482; Paul Richli, Grundriss des schweizerischen Wirtschaftsverfassungsrechts, 2007, pag. 94 segg. con ulteriori rinvii alla giurisprudenza).
Dato che la revoca in parola comporta una limitazione grave della libertà economica del ricorrente - nella misura in cui viene chiamato ad esprimersi in merito a tali aspetti, conformemente all'<ref-law> (cfr. precedente consid. 2) - il Tribunale federale esamina liberamente non solo il rispetto delle condizioni evocate, ma anche l'interpretazione e l'applicazione del diritto cantonale ad esse connesse (<ref-ruling> consid. 4.2.2. pag. 157 seg.; <ref-ruling> consid. 8.2 pag. 43).
5.2 Con riferimento all'art. 36 cpv. 1-2 Cost., la Corte cantonale ha correttamente rilevato come la misura di revoca ordinata poggi su una base legale sufficiente, costituita dagli art. 8 e 20 cpv. 1 LFid. Sempre correttamente, essa ha quindi evidenziato l'interesse pubblico perseguito attraverso la prescrizione del requisito dell'ottima reputazione cosi come concretizzato dall'art. 8 cpv. 2 lett. b LFid, osservando quanto permetta di limitare il libero esercizio della professione a quegli operatori che offrano sufficienti garanzie dal profilo dell'onestà nella gestione dei beni altrui e nella rappresentanza di terzi nell'amministrazione dei loro interessi patrimoniali (riguardo all'attività di fiduciario in base alla LFid cfr. per altro già sentenza 2P.142/1990 del 21 dicembre 1990 consid. 3b; cfr. inoltre sentenze 2P.309/2005 del 17 maggio 2006 consid. 3.1 e 2P.274/2004 del 13 aprile 2005 consid. 3.2).
5.3 Detto di queste due prime condizioni, il cui adempimento non era concretamente contestato neppure dal ricorrente, corretta dev'essere però considerata anche la sua conclusione in merito al rispetto dell'<ref-law>, norma che ricalca quel che prevede l'<ref-law>, facendo del rispetto del principio della proporzionalità un criterio specifico per ammettere la limitazione di un diritto fondamentale.
5.3.1 Nella misura in cui lo scopo principale degli art. 8 e 20 cpv. 1 LFid consiste nel fare in modo che possano operare nel settore professionale dei fiduciari solo persone che godono di ottima reputazione e garantiscono un'attività irreprensibile, i giudici cantonali potevano in effetti di principio considerare che, nel caso un fiduciario non adempia più ai requisiti previsti dalla legislazione in materia a causa di una condanna subita, sia pure necessario rispettivamente inevitabile che questi venga privato dell'autorizzazione per lo svolgimento di tale attività (sentenze 2C_655/2009 del 23 marzo 2010 consid. 4.7 e 2P.274/2004 del 13 aprile 2005 consid. 4.2 in fine).
5.3.2 A differenza di quanto sostenuto dal ricorrente, esaminando la correttezza della revoca decretata, i giudici cantonali - che non hanno per altro argomentato il loro giudizio solo riferendosi alla natura di permesso di polizia dell'autorizzazione in discussione - potevano però pure legittimamente lasciare aperta la questione a sapere se, dal profilo dell'<ref-law>, una condanna per reati intenzionali o per atti contrari alla dignità professionale debba portare, in ogni caso e sempre, a una revoca del permesso ottenuto oppure se, in determinate circostanze, il principio della proporzionalità richieda una valutazione differenziata.
Come nelle fattispecie oggetto della sentenza 2P.89/1990 del 21 dicembre 1990 (cui fa espresso rinvio anche il giudizio querelato) e della sentenza 2P.345/1990 del 7 ottobre 1991 - nelle quali il Tribunale federale è giunto alla stessa conclusione, lasciando aperta la questione posta - il ricorrente è infatti stato riconosciuto colpevole di un reato, commesso in ambito professionale, di natura tale da compromettere la fiducia del cliente e quella del pubblico in generale: nei due casi citati, la falsità in documenti (<ref-law>); in quello qui in esame, il conseguimento fraudolento di una falsa attestazione (<ref-law>), per aver indotto un notaio ad attestare in un documento pubblico un fatto d'importanza giuridica contrario alla verità; reati puniti entrambi con una pena detentiva sino a un massimo di cinque anni.
5.3.3 Occorre inoltre osservare come i giudici cantonali siano giunti ad ammettere la proporzionalità del provvedimento in esame tenendo anche correttamente conto di altri elementi quali gli effetti della revoca in termini di durata e il fatto che, per quanto incisiva, la misura presa non ha comunque come conseguenza un blocco totale dell'attività svolta dal ricorrente.
Da un lato, considerato che il periodo di cinque anni previsto dall'art. 8 cpv. 2 lett. b LFid viene computato dal momento della condanna penale (sentenza 2P.149/1999 del 20 dicembre 1999 consid. 3b.dd), hanno infatti a buon diritto sottolineato che - siccome il decreto d'accusa emesso nei confronti del ricorrente risale al 1° settembre 2008, la revoca è stata pronunciata il 2 settembre 2009 e i ricorsi in seguito interposti hanno sempre avuto effetto sospensivo - il provvedimento in discussione non avrà una durata di cinque anni, bensì di un lasso di tempo pari a poco più della metà.
Senza essere concretamente contraddetti in questa sede, se non in modo generico, gli stessi giudici cantonali hanno quindi pure rilevato come, per quanto gravoso, il provvedimento deciso non comporta per il ricorrente l'impossibilità assoluta di esercitare e come - anche nel periodo da qui al 31 agosto 2013, quando in base alla LFid la condanna non costituirà più un impedimento alla richiesta di una nuova autorizzazione - egli potrà eventualmente continuare a svolgere la sua attività in collaborazione con un fiduciario regolarmente autorizzato, nei limiti di quanto consentito dalla stessa LFid (sentenze 2P.290/2005 del 3 luglio 2006 consid. 5.4 e 2P.137/2001 del 17 luglio 2001 consid. 4e).
5.4 In considerazione degli aspetti evocati e della corretta ponderazione degli stessi da parte dei giudici cantonali, occorre concludere che il giudizio impugnato non risulta neppure lesivo della garanzia della libertà economica. Esso rispetta infatti tutte le condizioni poste dall'art. 36 cpv. 1-3 Cost. per la limitazione di tale libertà.
6. 6.1 Nella misura in cui è ammissibile, il ricorso va pertanto respinto, poiché infondato.
6.2 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.