I've had the same issue after wanting Gmail with my domain. This is what I found, your DNS is fine, you can check your google mail at:
once you set-up your email there and you can login as the admistrator, click on 'Manage My Domain' at the upper right, unless you are already there, then you can click the 'Service settings' menu head and 'Email' dropdown.
Then you can change the mail url to:
in the 'Web Address' under the 'General' tab, Let me know if this helps