Normally that is the message when accessing /Microsoft-Server-ActiveSync through the browser and not a phones mail client.
Is this what you are getting when using your phone?
This is saying that the user/device hasn’t been provisioned yet. If you remove the account from the phone and then re add it does it start working?