I had been running into this issue the past few days. I was using Visual Studio 2013 Professional and an iMac running Mavericks as my build host on the network. I was able to open Xamarin.iOS projects in Visual Studio, but as soon as I tried to execute it I would get this error. Google suggested that I make sure that both the Windows and Mac machines had been updated and that the product versions match on both sides. After checking and re-checking this I was about to give up and try to reinstall when I stumbled onto the answer.
In a post on the Xamarin forums, Brendan Zagaeski of Team Xamarin provided the information that would be the missing piece to my puzzle. His comment was in response to a different issue that a user was experiencing, but the part in bold was the key bit of information I needed.
…please try updating the clocks on both your Windows and Mac computer to the current accurate internet time. Part of security algorithm for the server-client communication requires that the clocks on both computers have closely matching times.
As expected, my Windows machine was synced with Internet time server time.windows.com and the iMac was synced to time.apple.com. For whatever reason, there was an 8 minute discrepancy between the times on the machines, which was apparently enough for the security algorithm to fail.
In order to prevent this issue from occurring again in the future I have set my Windows machine to synchronize with the same Internet time server as the iMac. Once updated and the clocks on both machines were in sync I was able to update the SDK on my Windows machine, allowing me to once again execute Xamarin.iOS applications from Visual Studio.