Fatti:
A. A._ e B._ sono comproprietari di un appezzamento di terreno di 151 m2, sito sul retro della loro casa di abitazione, attribuita alla zona di mantenimento dal piano regolatore di Lugano. Senza chiedere alcun permesso, agli inizi degli anni novanta, essi hanno costruito una sorta di gabbia (voliera), formata da una intelaiatura metallica di 47 m2, alta m 2,50, avvolta sia sui lati sia verso l'alto da una rete metallica a maglia. Su richiesta del Municipio, il 2 agosto 2004 i comproprietari hanno inoltrato un permesso in sanatoria, domanda avversata da alcuni vicini, tra i quali C._. Il 31 gennaio 2005 il Municipio ha negato il rilascio della licenza edilizia, decisione confermata in ultima istanza dal Tribunale cantonale amministrativo il 19 ottobre 2005.
B. Il 22 febbraio 2006 il Municipio ha ordinato la demolizione del manufatto eretto abusivamente. Per quanto qui interessa, il 22 agosto 2006 il Governo cantonale, con la partecipazione di un Consigliere di Stato, ha annullato l'ordine di demolizione, poiché adottato senza il previo avviso del Dipartimento del territorio. Adito dal vicino e dal Comune, con giudizio del 18 ottobre 2006 il Tribunale cantonale amministrativo ha annullato la decisione governativa e rinviato gli atti al Governo, affinché, raccolto il preavviso dipartimentale, si pronunciasse sul ricorso. Il 30 gennaio 2007 l'Esecutivo cantonale, astenuti due dei suoi membri, ha confermato l'ordine di demolizione. Adito dai comproprietari, con sentenza del 25 novembre 2009 il Tribunale cantonale amministrativo ne ha accolto il ricorso, la decisione governativa non avendo indicato la ragione delle citate astensioni. In seguito, il Consiglio di Stato ha nuovamente confermato l'ordine di demolizione, spiegando che una Consigliera di Stato aveva firmato il preavviso dipartimentale, mentre il Consigliere di Stato si era astenuto a causa del grado di parentela (cugino di secondo grado) con la moglie del comproprietario. Il 5 ottobre 2010 la Corte cantonale ha respinto nel merito il ricorso dei comproprietari.
C. Avverso questa sentenza A._ e B._ presentano un ricorso di diritto pubblico al Tribunale federale. Chiedono, concesso al gravame effetto sospensivo, in via principale, di riformarla nel senso di annullare la decisione governativa del 30 marzo 2010 e di rinviare gli atti alla Corte cantonale per nuovo giudizio, in via subordinata, di sostituire l'ordine di demolizione con una sanzione pecuniaria.
C._ dichiara di voler restare ai margini della procedura ricorsuale, il Municipio di Lugano propone di dichiarare inammissibile e subordinatamente di respingere il ricorso, il Governo non si esprime, mentre la Corte cantonale si riconferma nella propria decisione.
Con decreto presidenziale del 9 dicembre 2010 al ricorso è stato conferito effetto sospensivo.

Diritto:
1. 1.1 Il Tribunale federale esamina d'ufficio se e in che misura un ricorso può essere esaminato nel merito (<ref-ruling> consid. 1).
1.2 Presentato contro una decisione dell'ultima istanza cantonale nell'ambito del diritto edilizio, il ricorso in materia di diritto pubblico, tempestivo (<ref-law>), è di massima ammissibile sotto il profilo degli art. 82 lett. a e 86 cpv. 1 lett. d LTF (<ref-ruling> consid. 1.1). L'erronea denominazione del rimedio esperito quale ricorso di diritto pubblico, ritenuto che in concreto i presupposti formali del gravame sono di massima adempiuti, non può comportare un pregiudizio ai ricorrenti (<ref-ruling> consid. 3.1). La loro legittimazione è pacifica.
1.3 Secondo l'art. 42 cpv. 1 e 2 LTF, il gravame dev'essere motivato in modo sufficiente, spiegando nei motivi perché l'atto impugnato viola il diritto (<ref-ruling> consid. 1.4.1). Le esigenze di motivazione sono inoltre accresciute laddove il ricorrente lamenta, come in concreto, la violazione di diritti fondamentali e di norme del diritto cantonale (<ref-law>), nonché l'arbitrio nell'accertamento dei fatti e nella valutazione delle prove, poiché ciò equivale a sostenere che i fatti sono stati accertati in violazione dell'<ref-law> e del diritto federale (<ref-ruling> consid. 2.4 e 2.5; <ref-ruling> consid. 4.1). L'atto di ricorso adempie solo in parte queste esigenze di motivazione.
2. 2.1 Nella decisione impugnata si rileva che secondo le osservazioni del Governo cantonale, il Consigliere di Stato astenuto è cugino di secondo grado della moglie del ricorrente e, di conseguenza, risulta essere pure cugino, nello stesso grado, di quest'ultimo. Ciò in virtù del rinvio dell'art. 32 cpv. 1 della Legge ticinese di procedura per le cause amministrative del 19 aprile 1966 all'art. 26 del previgente CPC/TI, secondo cui l'interessato deve tra l'altro escludersi:
a) "se è marito, moglie, partner registrato, convivente, ascendente o discendente, patrigno o matrigna, figliastro o figliastra, fratello o sorella, fratellastro o sorellastra, zio o zia, nipote, suocero o suocera, genero o nuora, cugino o cugina, cognato o cognata di una delle parti o dei patrocinatori o procuratori;"
b) "se egli, o i suoi congiunti nei suddetti gradi hanno interesse nella causa o in altra vertente su identica questione di diritto".
La Corte cantonale ha stabilito che l'<ref-law>/TI non pone un limite al grado di parentela, rispettivamente di affinità tra cugini, fondante l'obbligo di astensione del membro dell'autorità chiamata a decidere, per cui il Consiglio di Stato, decidendo con soli tre membri, ha statuito nella composizione prevista nella legge.
2.2 Al riguardo, e meramente a titolo abbondanziale, i ricorrenti sostengono, in maniera generica, che il citato legame di parentela sarebbe stato indicato in modo errato, poiché la moglie del ricorrente e il Consigliere di Stato astenutosi avrebbero quale ascendente comune il bisavolo, essendo rispettivi nipoti di fratelli: il legame di parentela sarebbe pertanto non di secondo, ma di sesto grado. Ora, con questo semplice accenno essi non dimostrano che il criticato riconoscimento di un legame di parentela giusta l'<ref-law>/TI, segnatamente cugini di secondo grado, sarebbe avvenuto in maniera addirittura insostenibile e quindi arbitraria (art. 105 cpv. 1 e 2 e <ref-law>; <ref-ruling> consid. 1.2).
2.3 D'altra parte, circa la contestata applicazione dell'<ref-law>/TI, i ricorrenti si limitano ad addurre che l'elenco dei rapporti di parentela contenuti in detta norma sarebbe esaustivo e non esemplificativo e che tra essi non figurerebbe quindi l'asserito legame di sesto grado. Con questa argomentazione essi disattendono tuttavia, che in concreto la Corte cantonale non ha esteso il motivo di astensione a qualsiasi legame, ritenendolo semplicemente dato per i cugini di secondo grado, rientranti senza arbitrio nella citata norma.
3. 3.1 Riguardo al contestato ordine di demolizione, i ricorrenti insistono sulla loro asserita buona fede, sul preteso mancato rispetto del principio di proporzionalità e sulla sostenuta assenza di un interesse pubblico prevalente rispetto ai loro interessi privati.
3.2 In tale ambito, la Corte cantonale ha ricordato che l'art. 43 della legge edilizia cantonale del 13 marzo 1991 (LE), concernente la demolizione di opere eseguite in contrasto con la legge, non contravviene di regola al principio di proporzionalità. Ha poi rilevato che si può prescindere dal provvedimento di ripristino quando l'opera eseguita diverge solo in modo irrilevante da quanto autorizzato, quando la demolizione non persegue scopi di interesse pubblico, oppure se il proprietario poteva ritenere in buona fede che la costruzione fosse lecita e al mantenimento dello stato di fatto non ostino importanti interessi pubblici.
Nel merito, i giudici cantonali hanno stabilito che la violazione materiale della legge è stata accertata in maniera definitiva nella precedente decisione del 19 ottobre 2005. Riguardo al principio della proporzionalità, hanno ritenuto che l'opera litigiosa configura un elemento estraneo all'ambiente circostante, in contrasto con le norme che regolano l'attività edilizia in quel particolare tipo di zona, contrasto non irrilevante e non di mera natura estetica. Ne hanno concluso, che l'interesse pubblico al ripristino di una situazione conforme al diritto è evidente, rilevato pure che i ricorrenti hanno agito in mala fede, realizzando l'opera in esame all'insaputa dell'autorità. La circostanza che, al loro dire, un funzionario del Municipio avrebbe visto il manufatto nel quadro di un sopralluogo senza nulla eccepire, non sarebbe decisiva, non provenendo dall'autorità competente. Neppure l'asserita inattività di un altro funzionario potrebbe del resto essere considerata di regola costitutiva di una situazione acquisita intangibile o di un'autorizzazione tacita o di una rinuncia dell'autorità a far rispettare le norme trasgredite.
3.3 I ricorrenti insistono sul fatto che l'art. 30 delle norme di attuazione del piano regolatore comunale non esclude ogni intervento nella zona in cui si trova il loro fondo, permettendo la realizzazione di "arredi per giardino": per lo meno sotto il profilo soggettivo potevano quindi ritenere che il manufatto potesse non soggiacere all'obbligo di licenza edilizia. Essi ricordano che nella decisione del 2005, il Tribunale cantonale amministrativo aveva peraltro ritenuto "opinabile" la decisione del Municipio di non considerare detta opera come arredo per giardino. Ribadiscono poi che non meglio precisati funzionari del Comune avrebbero osservato la recinzione litigiosa, eretta nel 1992, e che con la dovuta diligenza avrebbero potuto intervenire tempestivamente. Affermano quindi la loro buona fede sull'assunto secondo cui l'opera abusiva sarebbe stata tollerata per svariati anni, motivo per cui non vi sarebbe un interesse pubblico alla sua demolizione.
3.4 I ricorrenti, rettamente, non contestano la sussistenza di una violazione materiale del diritto, accertata nel 2005, che esclude a priori qualsiasi procedura sanatoria a posteriori: ciò non implica tuttavia che l'opera abusiva debba necessariamente essere demolita, ritenuto che anche in questi casi occorre tener conto dei principi della proporzionalità e della tutela della buona fede (<ref-ruling> consid. 6 pag. 365; <ref-ruling> consid. 6 pag. 35; HÄNNI, Planungs-, Bau- und besonderes Umweltschutzrecht, 5a ed., 2008, pag. 343 segg.).
3.5 Già nella decisione del 19 ottobre 2005, non impugnata dai ricorrenti, il Tribunale cantonale amministrativo aveva stabilito che l'opera litigiosa, della quale peraltro i comproprietari non avevano mai chiaramente precisato la destinazione, era soggetta a permesso di costruzione, per cui essi nulla potevano dedurre in loro favore dal lungo tempo trascorso. Questa conclusione era ed è corretta. Il principio della buona fede (<ref-law>) tutela tra l'altro la fiducia riposta in un'informazione ricevuta dall'autorità, quando quest'ultima sia intervenuta in una situazione concreta rispetto a determinate persone, quando la stessa era competente a rilasciare l'informazione o il cittadino poteva ritenerla competente sulla base di fondati motivi, quando affidandosi sull'esattezza dell'informazione egli abbia preso delle disposizioni non reversibili senza subire un pregiudizio e quando posteriormente al rilascio dell'informazione non siano intervenuti mutamenti legislativi (<ref-ruling> consid. 6.1 pag. 636; <ref-ruling> consid. 8.1 pag. 60). Accennando semplicemente all'asserita passività di funzionari municipali, assunto peraltro definito come mera illazione da parte del Municipio nelle proprie osservazioni, i ricorrenti non dimostrano l'adempimento di siffatti estremi.
3.6 Secondo il principio della proporzionalità, non invocato in concreto in relazione a un diritto fondamentale specifico ed esaminato quindi sotto il divieto dell'arbitrio (cfr. <ref-ruling> consid. 4), le misure adottate dall'autorità devono essere idonee a raggiungere lo scopo di interesse pubblico perseguito e non eccedere i limiti dell'indispensabile (<ref-ruling> consid. 10.2 pag. 45). L'art. 43 LE prevede la demolizione delle opere abusive. Si può nondimeno prescindervi, quando l'opera eseguita diverge solo in modo irrilevante da quanto autorizzato, quando la demolizione non persegue scopi d'interesse pubblico, oppure se il proprietario poteva ritenere in buona fede che la costruzione fosse lecita e al mantenimento dello stato di fatto non ostino importanti interessi pubblici (<ref-ruling> consid. 6; cfr. sentenza 1C_403/2008 consid. 3 e 4, in RtiD 2009 I pag. 208).
Come visto, anche il proprietario che ha eretto in mala fede un'opera abusiva può invocare il principio della proporzionalità: in tal caso, nella ponderazione dei contrapposti interessi l'autorità per motivi di principio, ossia a tutela della parità di trattamento e dell'ordine in campo edilizio, può tuttavia attribuire un peso accresciuto all'interesse del ripristino della situazione conforme al diritto e trascurare o considerare solo parzialmente i pregiudizi e gli svantaggi derivanti all'interessato dall'ordine di demolizione (DTF <ref-ruling> consid. 6.4 pag. 39; <ref-ruling> consid. 4a).
3.7 In concreto, l'asserita assenza di un interesse pubblico riferita al lungo tempo trascorso è priva di fondamento. D'altra parte, i ricorrenti non si confrontano con l'argomento posto alla base del giudizio impugnato, secondo cui il manufatto configura un elemento estraneo all'ambiente circostante e in contrasto con le norme che regolano l'attività edilizia in questo particolare comparto, accennando in maniera generica semmai a un contrasto di mera natura estetica. La censura è quindi inammissibile per carenza di motivazione (<ref-law>), ritenuto comunque che la conclusione dei giudici cantonali non è peraltro insostenibile e quindi arbitraria (sulla nozione di arbitrio vedi <ref-ruling> consid. 1.3; <ref-ruling> consid. 4.1).
La legittimità dell'ordine di ripristino è quindi data, ricordato altresì che gli interessi pubblici al ripristino della situazione conforme al diritto prevalgono su quelli meramente finanziari e di comodità dei ricorrenti a evitare lo smantellamento della recinzione. La Corte cantonale ha infatti ritenuto che la rimozione dell'opera litigiosa è facilmente realizzabile, con costi contenuti. I ricorrenti non contestano questo accertamento.
3.8 Infine, la Corte cantonale, accertata una violazione del diritto sostanziale, la facilità e la proporzionalità della rimozione del manufatto, non ha esaminato oltre i presupposti per una sanzione pecuniaria sostitutiva. L'accenno di critica al riguardo è privo di fondamento, ricordato che l'art. 44 cpv. 1 LE prevede la possibilità di una sanzione pecuniaria soltanto quando la misura di ripristino risulti impossibile o sproporzionata.
4. Il ricorso, in quanto ammissibile, dev'essere quindi respinto. Le spese seguono la soccombenza (<ref-law>). Non si assegnano ripetibili della sede federale al vicino, che non si è espresso sul ricorso (<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'000.-- sono poste a carico dei ricorrenti.
3. Comunicazione ai patrocinatori delle parti, al Municipio di Lugano, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.