This wonderful heavenly Outlook message brings loads of joy to the user when he/she sees it. You could create a new Outlook profile, but there is a better way.
Click Windows Key+R to open Run dialog and type the following.
Outlook.exe /ResetNAVPane
It should resolve the issue by recreating the folders. If Yes, so say YES!!!
Anand, the Architect 
No. My error msg is slight different: “Cannot start Microsoft outlook. Cannot open the Outlook window. The set of folders cannot be opened. The information store could not be opened.” Any other suggestions?
Hi Ananad,
I tried typing in run , but it shows again create a new Outlook profile
No joy, still error message (before you get any options to reset folders). On a terminal server it seems to affect all users of that server.