I believe that you need to install Exchange 2003 SP 2 on your Exchange 2003 server.
Jaco said they did load Exchange 2003 SP2. Jaco, how many exchange 2003 servers do you have in your domain? If just one there may have been a time period for the change to update across the dc’s. Is this error still occuring?