I am just posting this as an FYI, so someone does not have to go through my hours of pulling out my hair. Searching the forum I found that this error was sometimes caused by dcom permissions.
However this was not the case in my situation. Although it might have been a combination of that and what I found
The culprit here was the machine had the Application pool set to run as a network service not a Local service. Once it was changed to a local service it worked like a charm. So If anyone else has this issue with an ASP.net page or webservice this could be the reason.