The naked domain cname problem is common. The dns specs do not allow you to redirect a naked domain. Because of this, many dns providers do not allow you to use a cname for @. Your dns providers way of making @ records use a CNAME must be interfering with other records.
Your workaround is as follows:
Google runs servers that do nothing but redirect naked domains to other domains (ie yourdomain.com to www.yourdomain.com) In your Google Apps control panel, go to Domain Settings -> Domain Name, and follow the instructions to redirect your naked domain to www.yourdomain.com. In your dns settings, have them keep your www record, but change the @ CNAME record to an A record: give them the ip addresses provided to you by Google in their instructions. Have them add Google's MX records and you're set.