Tente o seguinte:
Inicialize com o Ubuntu Live CD e abra um Terminal
Execute sudo fdisk -l
para obter o nome do dispositivo. Você terá algo como:
Disk /dev/sda: 250.1 GB, 250059350016 bytes
255 heads, 63 sectors/track, 30401 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Disk identifier: **********
Device Boot Start End Blocks Id System
/dev/sda1 * 1 30238 242886703+ 83 Linux
/dev/sda2 30239 30401 1309297+ 5 Extended
/dev/sda5 30239 30401 1309266 82 Linux swap / Solaris
Neste caso, o Ubuntu está instalado em /dev/sda1
. Então digite:
sudo fsck /dev/sda1
Reinicie o sistema e inicialize normalmente.