Fatti:
A. E.E._ e F.E._ sono proprietari del fondo edificato part. n. 41 di Rovio, situato su un terreno in pendio e confinante a valle anche con la particella n. 45 di proprietà di A.A._, B.A._, C.A._ e D._.
L'8 marzo 2005 i proprietari E._ hanno presentato al Municipio di Rovio una domanda di costruzione per edificare lungo il confine a valle del loro fondo un muro di sostegno in cemento armato. Il progetto prevedeva che il manufatto fosse alto da 0,35 m all'estremità ovest a 2,64 m all'estremità est. I confinanti A._ si sono opposti alla domanda, contestando l'opera essenzialmente per quanto riguarda la sua altezza. Con decisione del 19 settembre 2005 il Municipio ha sostanzialmente accolto l'opposizione, rilasciando la licenza edilizia alla condizione che il muro non superasse l'altezza di 1,50 m.
B. Rilevato che l'opera realizzata non era conforme a quanto autorizzato, il Municipio ha impartito agli istanti un termine per presentare una domanda di costruzione a posteriori. La nuova domanda è stata introdotta il 30 maggio 2007 e dal relativo piano di costruzione risulta che il muro sarebbe alto 1,65 m alla sua estremità orientale. I vicini hanno presentato un'ulteriore opposizione, che il Municipio ha tuttavia respinto il 17 ottobre 2007, rilasciando contestualmente la licenza edilizia in sanatoria. L'Esecutivo comunale al riguardo ha richiamato l'art. 10 cpv. 2 delle norme di attuazione del piano regolatore (NAPR), secondo cui, dove la situazione altimetrica del terreno lo richiedesse, i muri di sostegno possono essere alti fino a 3 m dal terreno sistemato.
C. Gli opponenti hanno allora adito il Consiglio di Stato del Cantone Ticino, che con risoluzione del 12 febbraio 2008 ha accolto il ricorso e annullato la licenza edilizia. Il Governo ha rilevato che l'altezza del muro di sostegno raggiungeva 2,25 - 2,40 m e che la pendenza del fondo non era tale da imporre, per consentire l'edificazione del fondo, l'erezione di muri alti più di 1,50 m.
D. Con sentenza del 9 dicembre 2008 il Tribunale cantonale amministrativo ha accolto un ricorso degli istanti in licenza, annullando la risoluzione governativa e confermando l'autorizzazione rilasciata dal Municipio. Secondo la Corte cantonale, il muro effettivamente realizzato supererebbe di poco, soltanto in prossimità della sua estremità est, l'altezza di 1,50 m e potrebbe essere autorizzato sulla base dell'art. 10 cpv. 2 NAPR.
E. A.A._, B.A._, C.A._ e D._ impugnano questa sentenza dinanzi al Tribunale federale con un ricorso in materia di diritto pubblico, chiedendo di annullarla e di annullare contestualmente la licenza edilizia. In via subordinata postulano il rinvio degli atti alla Corte cantonale perché completi l'istruttoria e si pronunci nuovamente sulla causa. I ricorrenti fanno valere l'accertamento manifestamente inesatto e incompleto dei fatti, nonché la violazione degli art. 9 e 29 Cost.
F. La Corte cantonale si riconferma nella sua sentenza. Il Consiglio di Stato e il Municipio di Rovio si rimettono al giudizio del Tribunale federale, mentre gli istanti in licenza postulano la reiezione del gravame.

Diritto:
1. 1.1 Presentato tempestivamente contro una decisione finale dell'ultima istanza cantonale, che ha sostanzialmente confermato il rilascio di una licenza edilizia fondata sul diritto pubblico, il ricorso in materia di diritto pubblico è di massima ammissibile sotto il profilo degli art. 82 lett. a, 86 cpv. 1 lett. d, 90 e 100 cpv. 1 in relazione con l'art. 46 cpv. 1 lett. c LTF.
1.2 I ricorrenti hanno partecipato al procedimento in sede cantonale. Quali proprietari di un fondo confinante con quello oggetto dell'intervento edilizio sono particolarmente toccati dalla decisione impugnata ed hanno un interesse degno di protezione al suo annullamento o alla sua modifica. La loro legittimazione a ricorrere giusta l'<ref-law> è pertanto data (cfr. <ref-ruling> consid. 1.3).
2. 2.1 I ricorrenti rimproverano alla Corte cantonale, tenuta ad accertare d'ufficio i fatti, di non avere eseguito alcuna istruttoria allo scopo di stabilire l'altezza del muro effettivamente realizzato, basandosi esclusivamente su una propria interpretazione delle fotografie prodotte dalle parti.
2.2 Secondo l'<ref-law>, i ricorrenti possono censurare l'accertamento dei fatti soltanto se è stato svolto in modo manifestamente inesatto o in violazione del diritto ai sensi dell'<ref-law> e l'eliminazione del vizio può essere determinante per l'esito del procedimento. Per essere manifestamente inesatto, e quindi arbitrario, il criticato accertamento deve risultare chiaramente insostenibile, in evidente contrasto con la fattispecie, fondato su una svista manifesta o contraddire in modo urtante il sentimento di giustizia e di equità (<ref-ruling> consid. 2.1, 129 I 173 consid. 3.1, 8 consid. 2.1 e rinvii).
2.3 La Corte cantonale ha ritenuto che il muro realizzato supera l'altezza di 1,50 m in misura limitata e unicamente in prossimità della sua estremità orientale. Non ne ha tuttavia concretamente stabilito l'altezza effettiva, esponendo una misurazione oggettiva basata su dati certi, che permettesse di verificarne la corrispondenza con la domanda di costruzione a posteriori. Né ha specificato quali sono i punti determinanti per calcolarla, precisando, in particolare a livello del terreno, da dove esattamente occorreva partire. Essa si è essenzialmente fondata sulle fotografie prodotte dalle parti, prive di qualsiasi scala o misurazione oggettiva, procedendo poi per deduzioni difficili da seguire e comunque non fondate su accertamenti precisi. In particolare, la precedente istanza ha dedotto dalle fotografie che il cassero in legno utilizzato per l'edificazione del muro sarebbe stato formato da due pannelli normalizzati, larghi 0,50 m ognuno, completati alla base e alla sommità da altre tavole larghe complessivamente quanto un ulteriore pannello. Premesso che la pretesa larghezza di 0,50 m del pannello utilizzato non risulta da uno specifico accertamento, né può essere ritenuta notoria, il calcolo dell'altezza del muro fondato sulle tracce lasciate nel cemento armato dalle tavole in legno risulta manifestamente approssimativo e superficiale. A maggior ragione ove si consideri che il progetto della domanda di costruzione a posteriori, indicante un'altezza dell'opera di 1,65 m in corrispondenza della sua estremità orientale, deve riprodurre la situazione effettiva e deve quindi potere essere verificato. Un accertamento puntuale dell'altezza, in particolare riguardo al livello del terreno da cui deve essere misurata, si giustificava pure alla luce delle contestazioni sollevate dagli opponenti e per il fatto che il Consiglio di Stato l'aveva addirittura considerata superiore ai 2,20 m. L'imprecisata altezza di poco superiore a 1,50 m è quindi stata rilevata dalla Corte cantonale in modo arbitrario, senza eseguire inappuntabili accertamenti sulla base della situazione di fatto.
3. 3.1 Secondo i ricorrenti, il Municipio di Rovio avrebbe applicato l'art. 10 cpv. 2 NAPR arbitrariamente, omettendo di esaminare le condizioni poste dalla norma, in particolare per quanto concerne la situazione altimetrica del terreno. Confermando la decisione municipale, la Corte cantonale avrebbe quindi negato a torto un abuso del potere di apprezzamento da parte dell'autorità comunale.
3.2 Anche questa censura è fondata. L'art. 10 cpv. 2 NAPR prevede in effetti che, dove la situazione altimetrica del terreno lo richieda, i muri di sostegno o di controriva possono avere un'altezza massima di 3 m dal terreno sistemato. Rilasciando il 17 ottobre 2007 la licenza edilizia in sanatoria, il Municipio ha semplicemente richiamato questa disposizione, adducendo in modo generico che la situazione altimetrica del fondo part. n. 41 avrebbe giustificato la costruzione del manufatto, il quale sarebbe conforme al diritto siccome alto meno di 3 m. L'Esecutivo comunale non ha tuttavia addotto alcunché riguardo alle caratteristiche concrete del terreno, contraddicendo peraltro in modo manifesto la sua precedente decisione del 19 settembre 2005, con la quale aveva negato la possibilità di un aumento dell'altezza in applicazione dell'art. 10 cpv. 2 NAPR, poiché volto unicamente ad incrementare la superficie pianeggiante del fondo. Dal canto suo, la Corte cantonale ha ritenuto sostenibile la soluzione adottata dal Municipio, confermando il rilascio della licenza edilizia in sanatoria sulla base di un'argomentazione inconferente, fondata sull'inclinazione del terreno da est ad ovest, in corrispondenza della lunghezza del muro, e sull'esigenza di mantenerne orizzontale la sommità. Essa non si è per contro espressa sulla "situazione altimetrica del terreno" ai sensi dell'art. 10 cpv. 2 NAPR, confrontandosi con le caratteristiche concrete del pendio, segnatamente per quanto concerne la pendenza della particella n. 41 sull'asse nord-sud. Trattandosi di un muro di sostegno, destinato quindi a sorreggere un terrapieno, la situazione altimetrica determinante si riferisce infatti essenzialmente al dislivello del terreno a monte del manufatto. L'autorità comunale e la Corte cantonale hanno quindi manifestamente disatteso la portata della citata disposizione, incorrendo nell'arbitrio.
4. 4.1 Ne segue che il ricorso deve essere accolto e la decisione impugnata annullata. Gli atti sono rinviati alla Corte cantonale affinché siano eseguiti più precisi accertamenti sulle caratteristiche della costruzione litigiosa e si pronunci nuovamente sulla causa con una motivazione esauriente, segnatamente per quanto riguarda l'eventuale applicabilità dell'art. 10 cpv. 2 NAPR.
4.2 Le spese seguono la soccombenza e sono quindi poste a carico degli istanti in licenza (<ref-law>), che rifonderanno ai ricorrenti un'indennità per ripetibili della sede federale (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto e la decisione impugnata è annullata.
2. Le spese giudiziarie di fr. 2'000.-- sono poste a carico di F.E._ e E.E._, che rifonderanno ai ricorrenti un'indennità di fr. 2'000.-- a titolo di ripetibili della sede federale.
3. Comunicazione ai patrocinatori delle parti, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.