Unable to receive email from one domain

A network administrator from one of our clients is unable to send mail from their Exchange 5.5 server to our Exchange 5.5 server. His email messages are returned with the following error message “Action: Failed; Status: 5.4.0 (other or > undefined network or routing status)”. He informed me that he thinks our DNS tables are the cause of the problem. Can anyone suggest some troubleshooting steps? Thank you in advance.