Inicie pelo modo recovery e opte pelo root com rede. No terminal:
apt-get update
apt-get upgrade
Tente também
dpkg --configure -a
Observe se /vmlinuz aponta para -> boot/vmlinuz-2.6.35-23-generic
e se /initrd.img aponta para -> boot/initrd.img-2.6.35-23-generic
com o comando
ls -l /vmlinuz initrd.img