Missing Intermediate Certificate in Certificate Chain

As promised, I will outline some of the issues I had with a recent Exchange 2010 migration. After Installing the required UCC and intermediary certificates on both the Exchange and ISA 2006 SP1 servers, following the GoDaddy instructions here, I ran into some issues. Namely ActiveSync refused to work. I headed of the best Exchange Connectivity Troubleshooting site EVAR! This gave me the following detailed info:

Validating certificate trust for Windows Mobile Devices
Certificate trust validation failed
Additional Details
Missing intermediate certificate in Certificate Chain. Subject =
SERIALNUMBER=07969287, CN=Go Daddy Secure Certification Authority,
OU=http://certificates.godaddy.com/repository, O="GoDaddy.com, Inc.",
L=Scottsdale, S=Arizona, C=US, See KB 927465 for more details.

After some serious troubleshooting, googling etc, I still didn't have the issue fixed. As a last resort I rebooted (thought those days were gone) the ISA server. Lo and behold it worked, but that's four hours of my life I'm not getting back anytime soon. What's weird about this is that it's the first time I've had to reboot a ISA server to get a certificate to "take". Oh well...