HDMI auto-negotiation seems to be a never-ending source of issues, with all manner of devices. I wonder if the HDMI specs include good reference code & pseudo-code for doing it properly. They need to make it so simple even a trained monkey could get it right. That, and robust conformance testing.
Heh, probably happens when enabling HDCP, and therefore could well be another HDMI auto-negotiation issue.
I've had problems like this with an old DVI monitor and different GPU. With problems like this, it's not always obvious which party is at fault, and sometimes the issue could be specific to the version of HDCP supported by the display.