New domain/email with Google Apps, can't receive mail.

[GSDog]

I just bought a new domain to use for emails only and have setup a Google Apps account and verified the domain, etc.

I can send emails from the new account but I get the following Delivery Status Notification (Failure) message when I try to send mail to the new account:

Delivery to the following recipient failed permanently:

[email protected]

Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 550 550 This domain is not hosted here (state 13).

Any idea what is causing that and why it cannot receive any mail?

 

[GSDog]

Just realized that I forgot to add the Google MX records to my domain host. I've done that now but still can't receive mail, does it usually take a while to update the MX records?