This morning our freshly installed SharePoint Server 2013 server was refusing to let me save a simple form with a Lookup column to another list. Using the standard insert/edit form, the error message read:
When using the quick edit mode, the error message was:
The fix turned out to be a
iisreset on the SharePoint server.
Update: It looks like the culprit is the Security Token Service, more info over at Sharepoint2013.me.
I hope this helps somebody else save a few hours of head scratching.