Exchange error (hr=0x80040115, ec=-2147221227)

I am posting this here because when i got this error. I opened MSN live and started searching for this. I couldn't find the solution and after debugging thru the code and with the help of a senior collegue when i finally was able find the solution i thought i will post it as a way of giving back !
So If you are hitting "Microsoft.Mapi.MapiExceptionNetworkError: MapiExceptionNetworkError: Unable to make connection to the server. (hr=0x80040115, ec=-2147221227)" read on.
You can hit it either through your code when you try to open a mailbox session using MAPI. OR using OWA, or even using send/recv of outlook. I was hitting it from code.
First thing, check that your Database i mounted, You can logon to the exchange admin console, or go to Powershell prompt and give "get-mailboxdatabase | fl Stat*"
Make sure the status is Mounted.
Next check your Microsoft Exchange Information Store service. Better yet, restart that and your Mailbox Submission.
The solution i think worked for me is purely my case. yours could be completely different.
If this doesnt work for you blog me and we can look at it :)