В ситуации с Ubuntu 12.04 было необходимо как вручную установить linux-headers-server и linux-server (как было предложено выше - я бы прокомментировал там, но еще не имею этой привилегии), а затем apt -get удалить linux-headers-virtual, который больше не существует как 64-разрядный пакет для 12.04.
sudo wget https://launchpad.net/ubuntu/+archive/primary/+files/linux-headers-server_3.2.0.64.76_amd64.deb