Is your desktop resolution set to the same resolution you run the game in? 16bit/32 bit? Try that first.
Re-install DirectX and see if that helps also. Other than that I would say it's a video driver problem, so you need to quote your adaptor type, and what flavour of drivers its using. You may get this problem if the adaptor refresh rate is not set to "optimal" and is using a custom setting. I use diferent resolutions from desktop with no problems but some driver setups don't like it.