No lo creía, pero es verdad. Después de lesear un buen rato con Wine y buscar en San Gugle, pude correr una versión (un tanto parcheada) de Starcraft.
Un consejo muy útil fue el que encontré aquí, en Linux Chile. Mejora bastante el rendimiento correr el servidor X sin el escritorio.
Aunque no lo he probado, revisen también Starcraft-wine. Parece que tiene buenos consejos.
Wine la lleva, después de todo ;)