Comment 5 for bug 1260264

For me, this issue was the result of an unsupported (non-PAE) cpu.

The workaround is fake-pae: https://launchpad.net/~prof7bit/+archive/fake-pae

sudo apt-add-repository ppa:prof7bit/fake-pae

sudo apt-get update

Now you need to manually install fake-pae because apt-get will give the "-f install" error

sudo apt-get download fake-pae
sudo dpkg -i fake-pake*.deb

It should install, after which you can do:
sudo apt-get -f install
sudo apt-get upgrade