Could you take a look at
http://support.microsoft.com/kb/907342
This appears to be similar, the problem is I'm using Office 97 so the suggested methods can't be used. Do you know what they mean by 'corrupted shortcut to the Office program that your trying to start' I've cleared all the existing shortcuts and remade them, and still get the same message.