Fatti:
A. Dopo aver stanziato un credito di fr. 1'150'000.-- per l'adozione di misure di moderazione del traffico e di riassetto urbanistico-viario in viale San Salvatore, il 25 settembre 2000 il Comune di Paradiso ha inoltrato il relativo incarto alla Sezione dei trasporti del Dipartimento cantonale del territorio al fine di richiedere i sussidi federali previsti per questo genere di interventi. Il 31 gennaio 2001 l'autorità cantonale ha informato il Comune che l'Ufficio federale delle strade (USTRA) le aveva notificato il preavviso favorevole dell'Ufficio federale dell'ambiente, delle foreste e del paesaggio ed aveva autorizzato l'inizio dei lavori. Dopo un incontro tra le parti, con lettera del 5 aprile 2001 l'USTRA ha confermato che i lavori potevano essere iniziati e che, ad eccezione degli interventi sull'illuminazione pubblica, il progetto era sovvenzionabile.
B. Il 14 luglio 2003 il Dipartimento del territorio ha segnalato a tutti i comuni che in base alle misure di sgravio 2003 delle finanze della Confederazione non sarebbe di principio più stato concesso alcun sussidio federale per le misure di moderazione del traffico. Il Comune di Paradiso si è allora rivolto dapprima alla Sezione cantonale dei trasporti ed in seguito direttamente all'USTRA, rilevando che a suo giudizio il sussidio per i lavori in viale San Salvatore, iniziati il 12 maggio 2003, doveva comunque essere garantito. Esso ha quindi preannunciato che avrebbe richiesto il versamento della partecipazione della Confederazione. Ribattendo ad una prima lettera del Comune, il 5 novembre 2003 l'autorità federale gli ha tuttavia confermato che il progetto in questione non avrebbe beneficiato di alcun sussidio.
C. Con scritto del 6 febbraio 2004 l'USTRA ha comunicato alla Sezione cantonale dei trasporti che in virtù della legge federale sulle misure urgenti del programma di sgravio 2003, adottata il 19 dicembre 2003 (RU 2003 5203), non sarebbe effettivamente più stato possibile finanziare i progetti previsti in una serie di comuni, debitamente elencati. Lo scritto si soffermava inoltre in modo particolare sulla situazione di Paradiso, rilevando che le misure di risparmio concernevano anche le opere di moderazione del traffico in detto Comune. Il 13 febbraio seguente la Sezione dei trasporti ha trasmesso la comunicazione dell'USTRA ai comuni interessati, ribadendone il contenuto.
D. Terminati gli interventi in viale San Salvatore, il 2 agosto 2004 il Comune di Paradiso ha inviato alla Sezione dei trasporti la liquidazione finale dei lavori, costati (senza l'illuminazione) fr. 1'321'777.--, con l'invito a trasmetterla all'USTRA affinché erogasse un sussidio pari al 55 % di detti costi. Il 6 settembre 2004 l'autorità cantonale ha dato seguito all'invito. Sollecitato dal Comune il 19 aprile 2005, l'8 luglio seguente l'USTRA ha ribadito alla Sezione dei trasporti che il progetto di viale San Salvatore non poteva essere finanziato.
E. Venuto a conoscenza di questa presa di posizione, con atto del 16 agosto 2005 il Comune di Paradiso si è rivolto tra gli altri all'USTRA, chiedendogli di riesaminare la decisione implicita insita nella comunicazione dell'8 luglio precedente, rispettivamente di emanare una decisione formale di diniego del sussidio. Con decisione del 24 ottobre 2005 l'USTRA ha tuttavia statuito di non entrare nel merito della richiesta di assegnazione di un contributo federale. A giudizio di detta autorità il rifiuto di qualsiasi sussidio era infatti già stato sancito nel proprio scritto del 6 febbraio 2004, che costituiva una decisione formale, ma contro il quale il Comune non era insorto tempestivamente. Ad ogni modo l'istanza sarebbe comunque stata da respingere in quanto non riguardava l'inammissibile revoca di un sussidio già garantito. Nessuna decisione di sussidiamento era infatti mai stata emessa.
F. Con sentenza del 25 giugno 2008 il Tribunale amministrativo federale, subentrato nelle competenze ricorsuali del Dipartimento federale dell'ambiente, dei trasporti, dell'energia e delle comunicazioni, ha respinto, per quanto ricevibile, il ricorso presentato dal Comune di Paradiso a tale Dipartimento contro la pronuncia dell'USTRA. L'autorità di ricorso ha in sostanza ritenuto legittima la decisione di non entrare in materia poiché l'istanza del Comune costituiva un tentativo tardivo di rimettere in discussione la decisione già comunicata il 6 febbraio 2004.
G. Il 25 agosto 2008 il Comune di Paradiso ha interposto un ricorso in materia di diritto pubblico dinanzi al Tribunale federale con cui domanda l'annullamento della sentenza del Tribunale amministrativo federale ed il rinvio degli atti all'USTRA. Dei motivi si dirà, per quanto necessario, nei considerandi.
Chiamati ad esprimersi, l'USTRA propone che il ricorso, nella misura in cui sia ammissibile, venga respinto, mentre il Tribunale amministrativo federale ha comunicato di rinunciare a pronunciarsi.

Diritto:
1. 1.1 In base all'art. 83 lett. k LTF il ricorso in materia di diritto pubblico è escluso contro decisioni concernenti sussidi al cui ottenimento la legislazione non conferisce un diritto. Determinante per valutare se una fattispecie ricade sotto questa clausola è il diritto applicabile nel merito, anche se, come in concreto, la sentenza impugnata è basata su motivi procedurali (sentenza 2C_370/2008 del 9 settembre 2008 consid. 1.1; sentenza 2C_18/2007 del 2 luglio 2007 consid. 2).
Secondo la giurisprudenza relativa all'abrogato art. 99 cpv. 1 lett. h OG e valida anche in riferimento all'art. 83 lett. k LTF (cfr. sentenza 2C_473/2007 del 18 settembre 2007 consid. 2.1), vi è diritto ad un sussidio se l'ordinamento legale fissa esso stesso le condizioni per la concessione della prestazione e non lascia quindi all'apprezzamento dell'autorità chiamata ad applicare la legge la facoltà di decidere se accordare o meno il finanziamento (<ref-ruling> consid. 3a; <ref-ruling> consid. 2a; <ref-ruling> consid. 1b; <ref-ruling> consid. 1b). Un diritto può peraltro sussistere anche se in base alla normativa applicabile i sussidi sono erogati soltanto nei limiti dei crediti autorizzati e soggiacciono quindi alla riserva che vi siano a disposizione fondi sufficienti (sentenza 2A.453/1996 del 18 agosto 1997 consid. 1b, in ZBl 100/1999 pag. 166; sentenza 2A.529/2005 del 20 aprile 2006 consid. 1).
Indipendentemente dall'esistenza di un diritto, per analogia con il regime previsto dagli art. 99 cpv. 1 lett. h e 101 lett. d OG, il ricorso in materia di diritto pubblico è in ogni caso esperibile qualora la controversia non riguardi la concessione o il diniego bensì la restituzione di sussidi già concessi, ovvero la revoca di una decisione attributiva di un vantaggio (sentenza 2C_266/2007 del 21 gennaio 2008 consid. 1.1, in RtiD 2008 II pag. 303; sentenza 2D_76/2008 del 16 marzo 2009 consid. 1.1).
Indipendentemente dall'esistenza di un diritto, per analogia con il regime previsto dagli art. 99 cpv. 1 lett. h e 101 lett. d OG, il ricorso in materia di diritto pubblico è in ogni caso esperibile qualora la controversia non riguardi la concessione o il diniego bensì la restituzione di sussidi già concessi, ovvero la revoca di una decisione attributiva di un vantaggio (sentenza 2C_266/2007 del 21 gennaio 2008 consid. 1.1, in RtiD 2008 II pag. 303; sentenza 2D_76/2008 del 16 marzo 2009 consid. 1.1).
1.2 1.2.1 Secondo quanto addotto dinanzi alle istanze precedenti dal Comune ricorrente, che non sembra peraltro avvedersi dell'art. 83 lett. k LTF, nel merito la vertenza concernerebbe la revoca di una decisione di sussidiamento già adottata e definitiva. In virtù della prassi menzionata, in tal caso il ricorso sarebbe quindi di massima ammissibile anche se in origine non vi fosse stato alcun diritto all'ottenimento del contributo federale.
1.2.2 L'USTRA ha tuttavia sostenuto di aver semplicemente autorizzato l'inizio anticipato dei lavori e confermato la sussidiabilità del progetto, ma di non aver mai formalmente garantito la concessione di un sussidio. Se così fosse, la via del ricorso in materia di diritto pubblico sarebbe data unicamente qualora sussistesse un diritto al contributo.
Il sussidio in questione è fondato sugli art. 25 e 26 della legge federale del 22 marzo 1985 concernente l'utilizzazione dell'imposta sugli oli minerali a destinazione vincolata (LUMin; RS 725.116.2), sull'<ref-law> (RS 814.01; cfr. anche RU 1984 1134 e RU 2003 5203) e sull'ordinanza del 25 aprile 1990 sui contributi per i provvedimenti resi necessari dal traffico stradale giusta l'ordinanza contro l'inquinamento atmosferico (RU 1990 695; di seguito: l'Ordinanza), abrogata dal 1° gennaio 2008 dall'ordinanza del 7 novembre 2007 concernente l'utilizzazione dell'imposta sugli oli minerali a destinazione vincolata (OUMin; RS 725.116.21; cfr. art. 34 n. 3 e art. 36 OUMin).
L'<ref-law> non prevede una semplice facoltà, ma sancisce, in forma non potestativa, che la Confederazione accorda contributi per i provvedimenti di protezione ecologica che, secondo la legislazione sulla protezione dell'ambiente, devono essere presi lungo le strade o negli edifici. L'Ordinanza definiva poi in maniera più dettagliata quali misure venivano sussidiate (art. 2), indicava quali spese erano computabili (art. 4) e fissava le aliquote di contribuzione che, almeno per le altre strade, erano stabilite mediante percentuali ben determinate (art. 3 lett. c e Allegato all'Ordinanza; cfr. anche RU 1997 1587 e RU 2004 4623). Gli uffici dell'amministrazione federale godevano di una certa latitudine di giudizio nella misura in cui erano chiamati ad esaminare l'opportunità dei programmi pluriennali allestiti dai cantoni riguardo ai provvedimenti previsti (art. 5 cpv. 3) e fissavano i crediti per ogni cantone in funzione dell'utilità dei provvedimenti stessi (art. 6 cpv. 2). Queste valutazioni riguardavano tuttavia la programmazione degli interventi e la gestione delle risorse finanziarie a disposizione. Entro tali limiti, le norme applicabili indicavano in maniera tutto sommato precisa le condizioni per la concessione di sussidi. In proposito non v'era quindi particolare spazio per il potere discrezionale dell'autorità.
Ne discende che nell'ambito in esame sussisteva con tutta probabilità un diritto a beneficiare di un sussidio federale. Il ricorso dovrebbe perciò risultare ammissibile anche se, come fatto valere dall'USTRA, nel merito la vertenza non riguardasse la revoca di una prestazione già accordata, bensì il rifiuto iniziale di concederla. Visto l'esito del gravame, in definitiva la questione può comunque rimanere aperta.
1.3 Dal profilo dell'ammissibilità dell'impugnativa può parimenti apparire dubbia la legittimazione a ricorrere del Comune di Paradiso. In effetti destinatari dei sussidi in materia di misure a tutela dell'ambiente rese necessarie dal traffico stradale sono di per sé i cantoni (cfr., in part., art. 1 e 10 cpv. 1 dell'Ordinanza). Il litigio non verte tuttavia sulla fondatezza materiale del diniego del contributo, bensì sulla legittimità della decisione di non entrare nemmeno nel merito della relativa richiesta. A prescindere da questo aspetto, il sussidio preteso si riferisce comunque ad un intervento viario su una strada comunale promosso e pagato dal Comune di Paradiso. Quest'ultimo è perciò direttamente toccato dal rifiuto del sussidio e persegue un proprio interesse finanziario degno di protezione (sentenza 2A.453/1996 del 18 agosto 1997 consid. 1d, non pubbl. in ZBl 100/1999 pag. 166; cfr. anche <ref-ruling> consid. 2.2.1; <ref-ruling> consid. 1.3). Esso è quindi legittimato a ricorrere, ai sensi dell'<ref-law>.
2. 2.1 Giusta l'<ref-law>, costituiscono decisioni i provvedimenti adottati dalle autorità in singoli casi, fondati sul diritto pubblico federale e concernenti la costituzione, la modificazione o l'annullamento di diritti o di obblighi (lett. a), l'accertamento dell'esistenza, dell'inesistenza o dell'estensione di diritti o di obblighi (lett. b) e il rigetto o la dichiarazione di inammissibilità d'istanze dirette alla costituzione, all'annullamento o all'accertamento di diritti ed obblighi (lett. c). Le decisioni devono essere notificate alle parti per iscritto (<ref-law>). Le decisioni scritte, anche se vengono notificate in forma di lettera, devono inoltre essere designate come tali, motivate e indicare il rimedio giuridico (<ref-law>). Una notificazione difettosa non può cagionare alle parti alcun pregiudizio (<ref-law>).
2.2 Secondo la giurisprudenza, il destinatario di una decisione non designata come tale e priva dell'indicazione dei rimedi giuridici non è legittimato ad ignorarla. Al contrario, se può riconoscere la natura di decisione e vuole evitare che il suo contenuto gli venga opposto, è tenuto ad impugnarla entro il termine di ricorso ordinario o ad informarsi in tempo utile riguardo al rimedio giuridico proponibile (<ref-ruling> consid. 3.3; <ref-ruling> consid. 2c; <ref-ruling> consid. 1c). Il medesimo obbligo sussiste se la decisione non viene notificata direttamente all'interessato, ma se costui in un modo o nell'altro ne viene a conoscenza (<ref-ruling> consid. 3.1.1). Certo, in base alla regola dedotta dal principio della buona fede ed espressamente sancita dall'<ref-law>, alle parti non può derivare alcun pregiudizio da una notificazione lacunosa dell'autorità. Tuttavia colui che ha riconosciuto l'inesattezza dell'indicazione dei rimedi di diritto o avrebbe potuto riconoscerla dando prova della diligenza da lui esigibile non può richiamarsi a tale principio. Questa eccezione trova comunque applicazione soltanto in caso di grave manchevolezza procedurale della parte interessata o del suo patrocinatore (<ref-ruling> consid. 3.3; <ref-ruling> consid. 1a/aa). Gli stessi principi valgono, per analogia, se, come in concreto, controversa è non solo l'indicazione dei rimedi di diritto, ma già il carattere di decisione di un determinato scritto (<ref-ruling> consid. 3.3; sentenza 2C_244/2007 del 10 ottobre 2007 consid. 2.5).
3. 3.1 Come già accennato, il 19 dicembre 2003 le Camere federali hanno adottato la legge federale sulle misure urgenti del programma di sgravio 2003, entrata in vigore il 1° gennaio 2004 (RU 2003 5203). Conformemente a quanto già segnalato a tutti i comuni ticinesi dal Dipartimento del territorio il 14 luglio 2003, tale normativa, mediante la modifica dell'<ref-law>, ha in particolare soppresso i sussidi federali per le misure contro l'inquinamento atmosferico, cioè per gli interventi volti alla moderazione del traffico, lungo le strade non classificate né come federali né come principali (cfr. il Messaggio del 2 luglio 2003 relativo al programma di sgravio 2003 del budget della Confederazione, FF 2003 4857 segg., in part. 4941, 4942 e 5009). Il 6 febbraio 2004 l'USTRA ha quindi segnalato alla Sezione cantonale dei trasporti le opere che, a seguito di questa revisione legislativa, non avrebbero beneficiato di alcun sussidio. La lettera precisava che le misure di risparmio interessavano anche il Comune di Paradiso e che a quest'ultimo era stata rilasciata unicamente l'autorizzazione all'inizio dei lavori ai sensi dell'art. 26 cpv. 2 della legge federale del 5 ottobre 1990 sugli aiuti finanziari e le indennità (Legge sui sussidi, LSu; RS 616.1), la quale non costituiva una garanzia per la concessione di sussidi.
3.2 Il Municipio di Paradiso ha reagito prontamente alla circolare del 14 luglio 2003. Già il 29 luglio seguente ha infatti segnalato alla Sezione dei trasporti che a suo parere le misure di risparmio non potevano incidere sui contributi per gli interventi in corso di realizzazione in viale San Salvatore. Di fronte all'avviso opposto espresso dall'autorità cantonale, ha poi ribadito la propria posizione in tre lettere inviate direttamente all'USTRA il 13 ottobre, il 25 novembre e il 23 dicembre 2003, ottenendo comunque il medesimo riscontro.
Al momento in cui ha ricevuto in copia lo scritto dell'USTRA del 6 febbraio 2004 il Comune è per contro rimasto inattivo. Dopo cinque mesi e mezzo, quando si è manifestato, esso si è peraltro limitato ad inviare i conteggi finali degli interventi operati, senza tuttavia menzionare, e quindi contestare, lo scritto del 6 febbraio 2004 e le risposte negative già fornitegli nei mesi precedenti sia dalle autorità cantonali che da quelle federali. Soltanto dopo diciotto mesi, ricevuta la lettera dell'USTRA che ribadiva il diniego del sussidio, ha poi chiesto l'emanazione di una decisione formale.
3.3 Eppure mediante la comunicazione del 6 febbraio 2004 l'USTRA ha sancito in maniera formale le conseguenze concrete dell'effettiva adozione delle misure urgenti contemplate dal programma di sgravio per quanto riguarda i progetti inoltrati dal Cantone Ticino. Con tale atto l'USTRA ha quindi ufficialmente respinto le domande di sussidio presentate dai comuni interessati, rispettivamente se tali domande erano già state accolte, come sostiene il ricorrente in riferimento alla sua situazione, le ha revocate. Di conseguenza, benché non avesse alcuna designazione particolare e fosse priva dell'indicazione dei rimedi giuridici, detta lettera costituiva una decisione ai sensi dell'<ref-law>.
Tale natura non può essere negata in ragione del fatto che lo scritto era indirizzato all'autorità cantonale e non ai comuni toccati dalle misure di risparmio. L'USTRA si è infatti giustamente rivolto al Cantone in quanto destinatario immediato dei contributi e quindi di per sé suo unico interlocutore. Il Cantone ha poi prontamente informato i comuni, non limitandosi per di più ad inviare per conoscenza la pronuncia dell'USTRA, ma riaffermandone espressamente le conseguenze. Con questa comunicazione la decisione dell'USTRA è pertanto stata notificata ai comuni interessati, di cui in definitiva respingeva le richieste. Il tenore della lettera dell'USTRA non si prestava inoltre ad equivoci di sorta. In particolare ne risultava chiaramente che anche il Comune di Paradiso, al pari di quelli di cui veniva stilato l'elenco, non avrebbe beneficiato in alcuna misura di contributi federali. È pertanto infondato sostenere, come pretende il ricorrente, che il carattere di decisione faceva difetto anche perché la lettera dell'USTRA veicolava incertezze sulle reali conseguenze finanziarie che il Comune avrebbe subito.
3.4 Considerati gli scambi epistolari avuti negli ultimi mesi del 2003 nonché la perentorietà dello scritto del 6 febbraio 2004, che si riferiva espressamente alla sua situazione specifica, il Comune di Paradiso non poteva non cogliere la portata di tale scritto. Anche se il medesimo era redatto in forma di lettera senza essere designato quale decisione e senza indicazioni sui rimedi giuridici, le autorità comunali avrebbero palesemente dovuto comprendere che in tal modo l'USTRA formalizzava, dopo l'entrata in vigore della necessaria base legale, il contenuto delle prese di posizione interlocutorie indirizzate loro, direttamente o indirettamente, nei mesi precedenti. Il Comune avrebbe perciò dovuto opporsi immediatamente a questa decisione, interponendo ricorso, informandosi sui mezzi di impugnazione esperibili o quantomeno reiterando le proprie rimostranze all'USTRA. L'omissione di qualsivoglia atto procedurale in questo senso va qualificata come una manchevolezza grave perlomeno nella misura in cui il ricorrente ha atteso quasi sei mesi prima di riprendere contatto con le autorità superiori ed ulteriori dodici mesi prima di richiedere l'emanazione di una decisione. Nonostante le lacune formali della pronuncia del 6 febbraio 2004, è quindi giustificato ritenere che il comportamento procedurale del Comune abbia comportato la preclusione della facoltà di contestare successivamente il mancato versamento del contributo.
Tale conclusione si impone anche se nelle lettere del 25 novembre e del 23 dicembre 2003 il Comune aveva preannunciato l'invio dell'incarto dopo la conclusione dei lavori per l'incasso del sussidio. La segnalazione di questa intenzione non liberava infatti il ricorrente dall'obbligo di impugnare tempestivamente la decisione del 6 febbraio 2004. Esso doveva comunque rendersi conto che con tale comunicazione l'USTRA si pronunciava in via definitiva sulla sua richiesta di sussidiamento e che in seguito all'autorità sarebbe bastato richiamarsi a questo scritto. Parimenti infondato è l'appello al principio della buona fede. In effetti, quand'anche potesse effettivamente confidare di essere al beneficio di una formale decisione che gli garantiva il contributo federale, il Comune non poteva ignorare che in tal caso la pronuncia del 6 febbraio 2004 rappresentava una decisione di revoca.
3.5 In base alle considerazioni che precedono, il rifiuto di entrare in materia sull'istanza del 16 agosto 2005, laddove questa chiede l'emanazione di una decisione formale di diniego del sussidio, non risulta lesivo del diritto. Lo stesso dicasi nella misura in cui l'istanza va trattata quale domanda di riesame del diniego. In effetti il ricorrente non fa valere alcuno dei motivi che, secondo la giurisprudenza, permettono di esigere la riconsiderazione di una decisione (<ref-ruling> consid. 6; <ref-ruling> consid. 3a; <ref-ruling> consid. 2b; sentenza 1P.513/2004 del 14 luglio 2005 consid. 2.1, in RtiD 2006 I pag. 11). Non occorre pertanto pronunciarsi sugli argomenti relativi al merito della vertenza sviluppati a titolo abbondanziale nella decisione dell'USTRA del 24 ottobre 2005, su cui del resto nemmeno il Tribunale amministrativo federale si è soffermato (cfr. comunque art. 26 cpv. 2, 2a frase LSu e sentenza 2A.453/1996 del 18 agosto 1997 consid. 2b, in ZBl 100/1999 pag. 166).
4. Ne segue che il ricorso in materia di diritto pubblico, nella misura in cui è ammissibile, deve essere respinto.
Secondo soccombenza, le spese processuali vanno poste a carico del Comune ricorrente, toccato dall'esito della causa nei propri interessi pecuniari (art. 65 e 66 cpv. 1 e 4 LTF). Non si assegnano ripetibili ad autorità vincenti (art. 68 cpv. 1 e 3 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 3'000.-- sono poste a carico del ricorrente.
3. Comunicazione al patrocinatore del ricorrente, all'Ufficio federale delle strade e al Tribunale amministrativo federale, Corte I.