Cannot connect to old Exchange 5.5 mailbox from AD domain

Hye,

We are in the process of going from an NT domain to Active directory.

The AD is built and trusts setup to the old domain. We can access file etc ok.

We have an exchange 5.5 server in the old domain but when we try to access it from the new domain we get the error

You do not have permissions to logon.

I have checked the account has the correct AD account allowed and also reset the permissions on the exchange server (NTFS) and they also look OK as far as I can tell.

Any ideas would be very helpful.