This error drove me nuts for about five hours before I found a solution that worked. I tried newer versions of wine, older versions of wine, puting various .dll files in my /windows/system folder etc etc etc, all with no results. Untill
I found this fix:

but if you've tried installing diablo II or other similar windows programs with
wine and run into this error, "no program start menu found" then this may
do the trick.

in console under x type:

wine regedit

this is wine's registration editor.

add a new string value (REG_SZ) to:

HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Explorer/Shell Folders

name the new string "Programs"
and give it the value "c:\windows\Start Menu\Programs"

that should do the trick
worked for me on Slackware 10.1, wine 20040121

thank you so much, i can now get starcraft with wine working

Nice, gg hf gl

um wheres the console under x b/c my friend gave me starcraft but it seems i cant change the cd key. everytime i try the message "no program start menu found" comes up plz help me if u have the answer email me at aguon1094@yahoo.com ty