Well, sometimes Wine just doesn't work very well. I haven't tried Starcraft with it, but I can suggest a couple things that have worked for me in Wine:
1. Use the source, rather than an RPM or other binary distribution of wine.
2. Use a fake-windows installation, rather than running programs on an existing Windows partition.
3. You have to run Wine in X, if you want any graphics, so shutting down X is not going to help
4. If all else fails, consider paying the nominal subscription fee for WineX (at http://www.transgaming.com
), since it is probably more likely to support games using DirectX than the standard Wine distribution.
Edit: Here is some info about running Starcraft in Wine: