If you receive “Invalid Product Key” in new install of Exchange 2013 CU3:
We were recently faced with one of these error messages in a new install (not an upgrade) for one of our clients, and we wanted to share the solution with your.
This happens when you setup a Hybrid deployment and you get the said error message after you enter the Product Key. The problem we found out has to do with a regression in within CU3, which recognizes the new install as invalid.
You can easily ignore this error and not waste any time troubleshooting. Your server is still licensed despite the error message. A fix will be forthcoming no doubt.