The caller was not authenticated by the service

Может вызываться недействительным сертификатом пользователя, либо таким сертификатом, который подписан ключом, сертификат которого отсутствует в Trusted Root.

Разумеется, в том случае, если клиент WCF аутентифицируется при помощи сертификатов