So I ran into this problem after re-installing Kubuntu 10.04 (for reasons that I shall not go into ::rolls eyes::).  Anyway, having an Nvidia GeForce 8400GS, I figured I could use the standard autodetection that Ubuntu provides for proprietary graphics drivers (described here) but for some reason that was not the case, so I needed to go in manually.

• First, using the terminal, I installed the latest nvidia drivers

sudo apt-get install nvidia-current

• Then, I restarted my computer and realized that my resolution was all wonky.  When I went into my “nvidia x server settings,” it told me that no such drivers were enabled.
• so I followed the directions in the error message and ran the following command:

sudo nvidia-xconfig

• Then I restarted my x server with the command 

sudo restart kdm

NOTE: the “kdm” is only because I’m running KDE.  If you’re running gnome it’s “gdm” and after 11.10 it’s “lightdm”

• then everything worked fine!