Yay, update, Got starcraft running like a dream on my debian 3 with a 2.6.7 kernel, tried running it through cedega 4.3.2, but it was very sluggish, however, i tried under wine, and it ran like a dream when i turned of color cycling and character portraits. It might just be me, but i get the feeling that the game runs better under wine than it does through cedega\winex.
Other issuses i had, was the sound came out kinda bad at first through wine when i used the alsa drivers, i then forced dsound hardware emulation:
"HardwareAcceleration" = "Emulation"
now it runs great, ive been trying for a while to get this to work, and i hope this will help others
note, havent tried networking yet, but my guess is it should work