This is what I've done.

apt-get update
everything updated just fine
apt-get upgrade
everything upgraded
apt-get install linux-headers-$(uname -r)
Building dependency tree
Reading state...