If you are really hardcore, you could reinstall windows xp again. As soon as finish, try starcraft. Do some patches, try starcraft again, and so forth.
You could also call your ISP and make sure nothing is gay on their end.
I don't believe you install a udp protocol. You could go to network connections > your network (most likely 'Local Area Connection') > properties and seeing what's there. Could install IPX just for lolz, it usually isn't there by default.

@rockz: Yes, I'm sure.
@isolatedpurity: I checked whats installed already, its how I noticed that udp was missing from the list. The only IPX protocol listed is NWLink/IPX/SPX/NetBIOS, description says it has something to do with NetWare servers. I checked with my isp, they said nothing has changed on their end. One of my partitions is still fairly empty, I'll resize it later today and install xp to attempt connecting from a completely fresh install.

UDP isn't in my protocol list either. I've never seen one either, ever.