You're not alone with this, seemingly epidemic. I've gotten it, and I've had it for a year or so. What I've done is:
1) Double-click Starcraft
2) Double-click Starcraft
3) Double-click Starcraft
4) Double-click Starcraft
5) Double-click Starcraft
6) Double-click Starcraft
7) Double-click Starcraft
8) Double-click Starcraft
9) Repeat steps 1-9 about 15 times.
10) Do something else for about 10-20 minutes.
11) Start up the game.
12) If error persists, try again.
That's what I do. If you don't have the time, I suggest just go and get a new disk and CD key.
Hope that help,s