I remember the same issues but don't know why we had to enable IPX/SPX over TCP/IP. I have a specific memory of troubleshooting for an hour and then clicked IPS/SPX and StarCraft worked.
Does anyone remember a specific reason why? I was too young to know or care.