It may be that one of the sources you have listed in your /etc/apt/sources.list is incorrect/out of date.
My recent install of Kubuntu had some updates, which I applied. This caused me no end of grief, because when the updates where released, some of the repositories/mirrors didn't seem to have all the packaged.
It took a lot of digging to find the answer, which was to add an additional repository/mirror to my sources.list file.
I'd suggest that you take a look at the Ubuntu sources.list generator
and get it to produce a new sources.list (move the existing one to /etc/apt/sources.list.old and then add the new one).
It may be worth making the change to the sources.list, but then remove the old version of the nvidia driver and then re-install the whole thing i.e.
sudo apt-get remove nvidia-glx && nvidia-kernel-common
and then do the opposite with
sudo apt-get install nvidia-glx && nvidia-kernel-common
The one thing I'm not sure of, is whether K/Ubuntu install the kernel-sources/kernel header files by default. The nvidia driver needs them usually, especially if you get the nvidia driver from the main www.nvidia.com
site and then run their installer i.e. sh NVIDIA-Linux-x86-*************pkg1.run - without the kernel-sources/headers it will "bin you out" every time!
If I've got a handle on what your problem actually is, then that should (in theory) do the trick.