Note: If the existing email service also incorporates a web front-end, the following instructions will not be sufficient - consult the email service provider and relevant documentation.
You can simulate the change on a testing box to confirm that any changes you plan to implement will work before you make any changes to the domain's nameserver settings.
On the new nameservers, duplicate the existing setup's MX records
On your testing box, set hosts file entries for the nameservers to point to the IP addresses of the new nameservers you've set up
On your testing box, flush the DNS cache and verify that the new nameserver records are being used (you can ping the domain name assigned to each nameserver - if the IP reported is the IP of your new nameserver as specified in the hosts file, you're set)
On your testing box, send a test email using SMTP (or telnet) - use a valid return address in case a bounce message is sent by the email service provider.
Confirm that the intended recipient has received the message
If you encounter errors while sending, research any error codes provided to determine the cause of the issue.
If the email is received, everything should be in working order to update the domain's nameservers without affecting clients with cached records or otherwise impacting email service.
If the email is not received and you did not receive an error while attempting to send or a bounce message at the return address you specified when you created the message, consult the email service provider to determine why the email was rejected (they should have a log of the attempt).
