You have to remove /etc/init.d/nvidia-glx by hand, even after doing apt-get remove nvidia-glx. The scripts removes /usr/lib/tls/libnvidia-tls.so.1.0.7184 and /usr/lib/tls/libnvidia-tls.so.1 at startup.
I further removed removed all Debian nvidia packages, but I do not know if that is necessary.
For the search-engines to find this hint:
My kernel is 2.6.8 (compiled myself from Debian kernel-source).
nvidia-installer used: NVIDIA-Linux-x86-1.0-7184-pkg1.run
Remark: For my Nvidia RIVA TNT I had to use the latest LEGACY-version from http://www.nvidia.com/object/unix.html
(Linux IA32); the "latest version" does NOT work. The error-message suggests the problem is with the kernels source or compiler, but that is not the case. Just get te legacy version. (If you use the wrong installation script you are notified to do so at start-up, but the installer script does not quit, so you might miss that message at first, as I did.)