Repositorios no accesibles

Saludos,

Soy algo nuevo en esto del ubuntu y ando algo perdido. Tras documentarme en varios sitios he llegado a la conclusion que el problema que tengo debe ser demasiado elemental y por lo tanto no se habla de ello :P

Mi principal problema es que no me deja instalar nada de nada. Por poner un ejemplo emass,

Los siguientes paquetes tienen dependencias incumplidas:
emacs22: Depende: emacs22-bin-common (= 22.1-0ubuntu5.1) pero no va a instalarse
Depende: libungif4g (>= 4.1.4) pero no es instalable
Depende: xaw3dg (>= 1.5+E-1) pero no es instalable
E: Paquetes rotos

Despues de horas de busqueda me doy cuenta que en lo de los repositorios me pone por ejemplo

# Line commented out by installer because it failed to verify:
# deb http://es.archive.ubuntu.com/ubuntu/ gutsy main restricted
# Line commented out by installer because it failed to verify:
# deb-src http://es.archive.ubuntu.com/ubuntu/ gutsy main restricted

Y asi la gran mayoria de los "enlaces", solo los ultimos estan sin comentar. Si quito la # para que sean accesibles y hago un update no me conecta con esos sitios y me dice,

W: Algunos archivos de índice no se han podido descargar, se han ignorado,
o se ha utilizado unos antiguos en su lugar.

El hecho es que inet si que tengo (de hecho escribo esto desde mi ubuntu) asi que ya no se que puede ser.

Es altamente desesperante la situacion asi que por favor si alguien sabe como solucionarlo le estaria eternamente agradecido.

PD: Perdonar el uso del lexico poco tecnico pero es que no ando de momento muy metido en el mundo. Gracias ^ ^

 EDIT: Apuntar que he formateado ya una vez y que desde el liveCD si que puedo acceder a esos paquetes, asi que supongo que porblema de la maquina no es.