Worst case scenario, you can access the X settings and add the resolution there. I don't think it should cause problems with the nVidia drivers. I had to do it that way when running Kubuntu under a virtual machine on my 1440x900 Macbook Pro. Scary process, but worked perfectly.
You may be able to do it more easily by editing the xorg.conf file, located in /etc/x11/ - I presume there are resolutions listed there, and you can type your desired one in. It should then become a selectable resolution.
I think the way I did it was by opening a terminal and typing
Code:
sudo dpkg-reconfigure -phigh xserver-xorg
It'll give you a screen with options unrelated to resolutions, just keep blowing through the screens without changing any of the settings (unless you know what you're doing) until you reach a resolution list. It has a long list of preset resolutions, and you just go through and mark the ones you want available. Worked for me. I still have my Kubuntu VM (but Parallels has garbage support for Linux, so I don't use it often) so I can verify this for you if you like.
Final note, those were the recommended instructions for people running Linux in a VM, largely under Parallels, where the graphics card is only emulated. I don't think it should make a difference whether it's a VM or not, but be aware.
I also noticed: switching to DVI or HD15 instead of using S-Video might help with the computer's auto-detection, but if you set the resolution manually, there'd be no need to bother with it.