I have periodically ran into the following exception on my CRM 2011 virtual dev machine:
System.ServiceModel.Security.MessageSecurityException: An unsecured or incorrectly secured fault was received from the other party. See the inner FaultException for the fault code and detail. ---> System.ServiceModel.FaultException: An error occurred when verifying security for the message.
I have found ways to work around this now every time I have ran into it.
I have noticed another Exception with the same cause before when working with the CrmSvcUtil.exe tool.
Cause: Timezone or time being wrong on the client or server.
Resolution: Correct date and time settings on affected machine, also restart client application making call
Example Post Illustrating: http://social.msdn.microsoft.com/Forums/is/wcf/thread/d7a13c9b-2144-4b0d-9585-5a487126ab1f
I had to restart Visual Studio on the client machine after I fixed the time on the server for my calls to function properly.
I hope this helps!