Pending setup: validating MX record

I bought a domain from Godaddy and then a few days later I purchased 100 email accounts. I set up 4 email addresses up fine. But now with every email account I set up I get this error:

(Pending setup: validating MX record)

I read the directions they gave me but when I go into my cpanel and try to find what I need to do the options are not there. I think the problem started to occur when I changed my name server on my domain so it will go to my forums. Is that what is causing this? I need this fixed soon so my staff can use their email accounts.