Right, I ran into this a while ago but completely forgot about it until now. After digging around a bit I found that there wasn't much documentation on this outside of the forums. So here goes:
This error occurs the first time the CrmService (or ICrmService) is envolked using a command like "Execute" or "Retrieve". What is meant to happen is that the service should connect to Crm based on it's "Unique Name", but a bug forces it to use the "Fieldly Name" instead. So consider this. You created a new organization on your Crm server called "My Crm Server", this is the friendly name, the Deployment Manager then auto-creates a unique name based on this, but without the spaces "MyCrmServer". Note that you can overwrite the unique name to make it anything else, so long as it doesn't contain non alphanumerics.
It seems to the end user that the organization got created without any problems and everything goes fine.
You write your first plug-in for the organization and deploy it. Your surprised to receive the "The request failed with HTTP status 401: Unauthorized" error and cannot find the cause of this error. Then, after you do a lot of debugging, you realize that it is in fact a Crm bug and not a bug in your code.
To fix this, there are one of two options.
1. From the deployment manager, disable the organisation and rename the friendly name to be identical to the unique name and then re-enable the org.
2. Install the patch: http://support.microsoft.com/kb/948746
Hopefully this helps those who, like me, struggled hours to figure this out.