Cannot display this video mode

The message is from what ? Monitor, PC Bios or Windows ? Did it start up all of a sudden, is it a new monitor, new video card ?

Check the native resolution for your monitor, then start the PC in safe mode, set the resolution to 800x600, reboot. Go to Control Pannel, Display, Settings Tab. Set the resolution to match your monitor. If it's an LCD, set refresh to 60, if it's a CRT, set it to 75.