email woes

Forgive me if this is in the wrong place...

I am having a problem getting my email to work with my domain. I have changed the MX record to reflect the mailserver my host gave me, but I still cannot RECEIVE email at any of the email accounts I have through the host. I can SEND email from the account, but cannot RECEIVE. I put a support ticket in with the host and the domain registrar, they're blaming each other... What am I missing?

The error was between the chair and keyboard here...

Either it just took time for the MX record change to propagate, or the CNAME record referencing the email server I changed in addition to the MX record did the trick. :)