This error happens in Xamarin when you have a newly setup environment, or you've recently downloaded your Apple Developer Certificate. Here are the steps you take to correct it.
1. First, thank your luck stars that you found this post
2. Go to KeyChain Access on your Mac
3. (select the Lock icon to unlock these items so that you can make changes)
4. Ensure the login section is selected on the left
5. Click each item individually and change the "When using this certificate" to Use System Defaults. Specifically make sure you change these: iPhone Developer, Mac Developer and Apple Worldwide Developer Relations Certification Authority
6. Close and Restart Xamarin and you should be apple to deploy.