Oh goodie. For the non-graphical out there:

ActiveSync cannot log on to Microsoft Outlook. Make sure Microsoft Outlook is installed and functioning correctly. You may need to restart your computer. You could have a conflict due to two folders on this computer are named C:\Program Files\Microsoft and C:\Program Files\Microsoft Office. If so, rename the C:\Program Files\Microsoft folder so that it does not contain the word “Microsoft.” If this folder contains subfolders, you may need to reinstall programs in the renamed folder. For more information on renaming folders and installing programs, see Help for your operating system.

I’ve got a better idea. How about I rename my Operating System so it no longer contains the name “Microsoft”, hmmm?

Update: A reboot fixed the problem.  So, don’t panic, just reboot - It’s Microsoft!