Hey, I did the EXACT same thing this morning with no problems. Here is what I did, it may help...
Download Nvidia binary NVIDIA-Linux-x86-1.0-8178-pkg1.run from the nvidia site (or the most recent version)
open synaptic (if you can) and uninstall anything that mentions nvidia, including kernels
Install the following via synaptic:
linux-headers-2.6.15-1-686 (for my machine anyway)
Press Ctrl+Alt+backspace to kill X (may need to do it more than once)
# cp /home/downloads/NVIDIA-Linux-x86-1.0-8178-pkg1.run /usr/local (or wherever you downloaded to)
# cd /usr/local
# sh NVIDIA-Linux-x86-1.0-8178-pkg1.run
Follow the instructions, don't download the headers, it should compile against the headers you have already installed.
Should work, you can tell if the nvidia logo appears
I have 1,700fps
Be aware that you current issue may be related to your grub configuration
# gedit /boot/grub/menu.lst
And have a root around there
Post back if you have continuing problems, I found it a little tricky at first