What a crazy error. I spent two hours on this today! What ended up happening was that my machine ran it's Windows Time update and my web server did it's...they updated to be 15 minutes apart! This caused my messages to stop working! Man...wish the auth error had bubbled up the stack! You have to add settings to the service side to get it to log the error, otherwise you will never know what is going on! Reference this to see how to add the configuration value:
<serviceSecurityAudit auditLogLocation="Application" serviceAuthorizationAuditLevel="Failure" messageAuthenticationAuditLevel="Failure" />
http://msdn.microsoft.com/en-us/library/ms731694.aspx
Chris