Fatti: A. Il 12 luglio 2007 lo Studio di architettura A._Sagl ha presentato al Municipio di Locarno una domanda di costruzione per l'edificazione di due stabili, uno di tre appartamenti e l'altro di cinque, sul fondo part. n. 1329 di Locarno, di proprietà della B._SA. La particella è ubicata su un pendio ai Monti della Trinità ed è compresa tra una stradina pianeggiante, denominata "sentiero centrale", e un ramo del medesimo sentiero che scende verso valle. Gli edifici sono accessibili dal "sentiero centrale", dal quale un montacarichi per autovetture consente di raggiungere un'autorimessa sotterranea comune. C._, proprietaria di fondi situati nelle immediate vicinanze, si è, tra altri, opposta alla domanda. Dopo il preavviso favorevole dell'autorità cantonale e l'inoltro di due varianti, il 26 marzo 2008 il Municipio ha rilasciato la licenza edilizia per il progetto modificato come alle varianti. L'esecutivo comunale ha nel contempo respinto l'opposizione della vicina. La decisione municipale è stata confermata il 14 ottobre 2008 dal Consiglio di Stato del Cantone Ticino su ricorso dell'opponente. B. Adito dall'opponente, il Tribunale cantonale amministrativo ne ha accolto il ricorso con sentenza del 19 gennaio 2009, annullando sia la licenza edilizia sia la risoluzione governativa che la confermava. La Corte cantonale, evase altre censure attinenti ad aspetti processuali e di merito, ha in particolare accertato che il piano del traffico del piano regolatore comunale qualificherebbe il "sentiero centrale" come semplice percorso pedonale. Ha quindi ritenuto insufficiente l'accesso al fondo dedotto in edificazione, essendo precluso alla circolazione veicolare. C. Lo Studio di architettura A._Sagl e la B._SA impugnano questa sentenza con un ricorso in materia di diritto pubblico al Tribunale federale, chiedendo di annullarla e di rinviare gli atti alla Corte cantonale per un nuovo giudizio. I ricorrenti fanno valere la violazione del divieto dell'arbitrio, della garanzia della proprietà e dei principi della legalità e della parità di trattamento. Lamentano inoltre un accertamento manifestamente inesatto dei fatti. D. La Corte cantonale rileva che la qualifica di percorso pedonale attribuita al "sentiero centrale" è scaturita dalle indicazioni fornite dall'Ufficio tecnico comunale. Precisa di avere preso atto solo in seguito al ricorso in esame dell'esistenza di un altro piano del traffico, nel quale l'opera viaria verrebbe classificata in modo ibrido quale percorso pedonale e strada di servizio ad orientamento pedonale. La Corte cantonale rileva che il suo giudizio sarebbe stato diverso se fosse stata portata a conoscenza di questa circostanza. Il Municipio di Locarno sostiene che il fondo dedotto in edificazione sarebbe urbanizzato, siccome dotato di un sufficiente accesso veicolare: il "sentiero centrale" presenterebbe infatti, secondo il piano regolatore approvato dal Consiglio di Stato il 16 gennaio 1996, una definizione mista di strada di servizio ad orientamento pedonale (SS2) e di percorso pedonale. Al giudice delegato del Tribunale cantonale amministrativo sarebbe invero stato sottoposto un piano successivo, approvato il 24 febbraio 1999, che non riprodurrebbe tuttavia correttamente la situazione effettiva. Il Comune produce al riguardo la documentazione a sostegno della sua argomentazione. Il Consiglio di Stato si rimette al giudizio del Tribunale federale, mentre l'Ufficio delle domande di costruzione del Dipartimento del territorio comunica di non avere osservazioni. L'opponente postula invece la reiezione del gravame nella misura della sua ammissibilità. I ricorrenti hanno ribadito le loro conclusioni il 29 maggio 2009.