Had a similar problem on older drivers with some doom port (SDL parachute deployed) - the problem was either to do with palletized textures, or the right resolution not being available. Try to
a. Disable palletized textures in whatever game you're using
b. Make sure that common resolutions like 800x600 and 640x480 are available for fullscreen switches...