During the Hosted Exchange (or HMC) installation process, you have to run the makeGalLinked.exe utility.  Now this should be done before you actually install Exchange, at least per the docs.  Now I made the mistake of installing Exchange first and then going through the rest of the solution documentation.  My fault, but how do you get around this?  Make sure you run this on the Active Directory server (which by the way should be a Windows 2003 Server).  Below is the error (It will have a Red background when ran from the Command Line):

There is at least one instance of globalAddressList attribute on object:CN=Microsoft Exchange, CN=Services,CN=Configuration, DC=<Your Domain>

Please backup and delete these instances before running this tool Aborting...

The way I got around this is to delete an entry (it's a multi-valued field, but there is only one currently in there) in the Configuration container of Active Directory.  This can be done using ADSI Edit which is a utility found on the Windows 2003 CD. 
So to do this, I installed the Windows 2003 Support Tools found on the Windows 2003 CD.  After the Windows 2003 Support Tools are installed, you can follow the below steps to add ADSI Edit to a new MMC, add the "Configuration Container", Navigate to the Microsoft Exchange object and remove the appropriate value(s) from the "globalAddressList" attribute.

1. Start>Run>"MMC">OK
2. File>Add/Remove Snap-in>Add.
3. Select "ADSI Edit".  Click Add, OK
4. Right-Click "ADSI Edit" and select "Connect To"
5. From the Connection Point pane, select "Select a well known Naming Context".
6. Select "Configuration"
7. Click OK.
8. Navigate to Configuration>Services>Microsoft Exchange (Reference the screenshot above.)
9. Right-Click on "Microsoft Exchange" and select "Properties"
10. Select "globalAddressList" and click the Edit button.
11. Click on a value (There should only be 1...no this is not a reference to Highlander!) and then click on Remove.
12. Click OK.

If you run the makeGalLinked.exe utility correctly, you should see the below screen.  Note:  You should see two green highlighted areas of text and the LOG_PASS line should read "100%"