I offer web hosting and my client ran into an issue with ME (Microsoft Exchange). He bought his domain from godaddy and his ME worked just fine when parked at godaddy. When I changed the nameservers over to my hosting, he ran into issues. He could no longer receive mail to his email with ME. Then he lost all his contacts and it turned into a mess. I decided to change the nameservers back to godaddy and his emails worked and he got all his stuff back. After contacting my reseller support they changed the MX Entry in his cpanel on my host and said that would solve the problem. I am currently waiting for the nameservers to propagate back to my server. Is there anything I am missing, I am very new to this Microsoft Exchange thing and I have never run into this before. Any help would be appreciated.
Your best bet is to review the DNS settings on the customer's old nameserver before pointing them to yours. Exchange uses several different records that are required to be setup in order for it to work. In addition to the MX record, there may also be SPIF records, DKIM, autoDescovery, among others. I would ask your customer for a screenshot of their current DNS zone file with GoDaddy (if you do not know how to dig for this information) and match the records, updating any relevant information.
If you're propagating that to your nameservers, then them changing MX records won't do anything because your customer will not be using GoDaddy DNS anymore, they'll be using yours.
So you just need to make sure the MX and A records are duplicated on your DNS zone. If you're not hosting the Exchange server, the only difference between your servers and GoDaddy's servers are the DNS configuration if the customer is using an external Exchange server.