I had the same problem installing vmware tools on ubuntu 12.10.

This didn't work for me:
$ sudo apt-get install gcc build-essential kernel-headers-$(uname -r) dkms

Instead, this did the job:
sudo apt-get install linux-headers-$(uname -r)