I have solved the problem. I'm posting a reply here in case someone else faces the same issue.
The solution was very simple. I needed to make sure that the cross-realm authentication principals were created with a single encoding type, of type rc4-hmac:
addprinc -e rc4-hmac krbtgt/AD.EXAMPLE.COM@EXAMPLE.COM
addprinc -e rc4-hmac krbtgt/EXAMPLE.COM@AD.EXAMPLE.COM
As far as I can tell, what happens is that the MIT KDC uses the most secure encoding type when sending the ticket to the AD server. The AD server is unable to handle that encoding and thus replied with the error that the encryption type is not supported. By only having a single encoding type for the principals, the MIT server will use that type when talking to the AD server.
Fair warning, my knowledge in this area is extremely dated at this point. Like early 2000's, Windows 2003 era Active Directory. So things may work differently now.
The main problem is that Windows doesn't know how to find the KDC for your MIT realm by default (ironically, it won't just use DNS to look it up like it does for AD). There's a utility called ksetup.exe that will let you map a realm name to one or more KDC servers. Ultimately, this utility is just setting some registry values. So you can automate this with Group Policy if necessary.
Update: @grawity mentioned that Windows may actually be able to find the KDCs via DNS as long as the proper SRV records exist and ksetup has been used to at least define the realm.
We also had what were essentially "shadow" accounts in AD that matched the users defined in the MIT realm. The passwords on those accounts didn't matter, they just had to exist. We may have also set some additional attributes like UPN or SPN that were related to the MIT realm in some way. Memory is hazy though.
Another thing to be aware of is the supported encryption types between AD and your MIT realm. If both are pretty recent, you'll probably be fine. But when we were doing this, our MIT realm was old and we had to add Group Policy in AD to add some legacy encryption types that the MIT realm supported.
Hopefully this should get you going in the right direction.
Best Answer
To answer your question you posed in the comments and the original question:
http://blogs.technet.com/b/canitpro/archive/2014/06/03/step-by-step-configure-vnet-to-vnet-connectivity-in-azure.aspx
You would establish a vnet to vnet VPN tunnel to allow that cross cloud service connectivity between the two forests. Then you could setup the trust relationship as normal.