failsafe mode? What exactly is that? Is it when your select safe mode or something when you boot up?
Is the module nvidia loaded into memory after you fail to make it into X?
does a lsmod show it? And if it doesn't try the command, depmod. Does that return any errors? Try to insert it manually into memory, by modrpobe nvidia.
check the entries in your Xfree86 log in your /var/log folder. Does X use the same exact configuration file when it works vs when it doesn't. It should say something like "using /etc/X11/XF86Config-4" or something like that.
Also check the output of the dmesg command. Right at the beginning it should tell you the name of the kernel that is being used. If you have to go all the way back to reboot to get into failsafe mode it may be that you are using a updated kernel or something for the regular mode, but you go back to the original kernel from the CD for the failsafe stuff. You may simply have to reinstall the NVidia drivers for the new kernel. Each kernel you use would have it's own /lib/modules/kernel-name folder.