You do not mention whether you have installed the Active Directory Connector. Exchange 5.5 stores all of its information locally in its own directory. Exchange 2003 looks exclusively to the Active Directory for most of its information. There are also permissions that need to be in place for the two system to talk. Here is a good Technet article for you to review:
Walk through it and make sure that you have executed each of the steps – I am guessing you will find a couple you missed and be able to correct the problem without too much trouble.