Does xdpyinfo | grep VidMode come back with anything? If so, what?
It may be that the VidMode extension isn't loaded. If you set Q3 to use the same resolution as your desktop is set to, does it work then?
If it does say that VidMode is loaded, then do you have more than one resolution in your Screen section in XF86Config-4? You need the various resolutions that Q3 uses (very likely 640x480 at least, and probably others as well) listed as alternatives. Actually, just post your entire Screen section.