Also, I've found that if you modify the default "mail.domain.com" record sometimes cpanel doesn't seem to realize that you've changed the default MX. To change the incoming SMTP server (MX) for a domain, I'd do two things (assuming the IP address for the SMTP server is 200.200.200.200):
1. Create a DNS A record mailserver.domain.com with IP 200.200.200.200
2. Use the cpanel MX changer to point the MX record to mailserver.domain.com.
These two steps, if they both work, are all that's required, I've done it lots. You don't need another MX, it really adds very little.
Never, ever point MX records to IP addresses - while it works for about 95% of incoming email, it breaks agreed Internet email standards and will prevent some people from emailing you. You don't want to cause this sort of obscure pain for yourself!
After using the cpanel MX function, if you have server login access, or know how to write a simple PHP script, you should check that domain.com has been removed from /etc/localdomains and put in /etc/remotedomains. Cpanel's Exim will try to process mail for domains listed in /etc/localdomains itself, so unless the domain.com line is removed and put into /etc/remotedomains, it just won't work for you. It's worth checking that cpanel is getting this right, because as I said above, it wasn't for a few months back earlier this year - I think it gets it right now.
Once you've made the changes, go to
www.dnsstuff.com and use the top right column to check the MX record definition has changed. If it hasn't, check your DNS settings in WHM's "Edit DNS Zone". If that still doesn't fix it, try either editing again, or getting the server admin to restart your server Bind. (probably unlikely you'll need to do either, it should work).