So I am working with a federated customer, attempting to put Exchange Server 2003 into an agency-level administrative group.  All the permissions at the 5.5 Org, Site and Config levels have been validated, the domain was an in-place upgrade and everything should be running just smoothly.  As we attempt to join the new server to the existing site/admin group, we enter the password and receive the following error:

This account must be valid before continuing

Not too helpful.  The account is not disabled, locked out or otherwise problematic.  Turns out, however, that two other factors must be met for Exchange 2003 to continue.  First, the password of the service account must meet with the domain password requirements.  So in our case, we changed the password on four 5.5 servers but the error message continues. 

Remember that little-used feature that was quite prominent in Windows NT 4.0, but somehow became buried after Windows 2000?  The one that allows you to restrict which machines an account can logon to?  Turns out that this customer had restricted the 5.5 service account such that it could only log onto 5.5 servers, forgot they had done that, and never bothered to add the 2003 servers to that list.  So, we added them and, voila, the account was suddenly valid again.

I could rant about the utility of this error message, but I feel that the knowledge from my lesson learned would go further to help others that encounter this issue.  But then again, why couldn't Exchange 2003 just say, "the selected account doesn't have rights/permissions to the local machine [machine name]?"