If you are hitting the wall using Plesk, just making changes to Plesk will not be enough. You have to change the DNS setting in control panel of your Name Server provider.
- You have to log in to your Server Command Control panel — which will be with your hosting provider and is is separate and distinct from PLESK. So you have to go to this panel and there you manage the DNS settings for your domain.
- Add the MX records as provided in the generic instructions for Google Apps. Make sure that you set the MX pointers to .yourdomain.com. and not to mail.yourdomain.com. The mail.yourdomain.com. record will not work correctly. Here is an example: