Hace poco tuve el mismo problema instalando algunos paquetes para compilar en un Ubuntu Server 6.06. No recuerdo cual era el paquete que necesitaba, pero lo solucioné usando en el mismo comando apt-get todos los paquetes que apt se quejaba de dependencias.
Código:
apt-get install <paq1> <paq2> <paqn>
Y ahora que lo veo, volve a poner el sources.lst como lo tenias antes porque me parece que quedo mal armado.