Apple has intentionally broken third party syncing services. From what I gather in the press, it's an ego battle going on with Google, but third party vendors are suffering.
You cannot, absolutely cannot, use iCloud and sync to Google Apps.
Spanning Sync and Soocial (both of which used to support very nice services in this regard) are out in the cold. I have both, well, had both -- neither has been able to solve the problem. Basically you have to choose between using Apple cloud (iCloud) or someone else's cloud (such as Google). Unfortunately, that means you can either have seamless syncing between all you Apple gizmos... or, you have to take a more manual approach.
So, if you want the more manual approach, here are a few tips:
1. Turn off iCloud for calendars and contacts on your computer.
2. Disable any kind of iCloud syncing for calendars and contacts on your devices, too.
3. I deleted all the contacts/calendar databases from my mobile devices (well, it happens automatically when you disable the iCloud syncing).
4. Now, on your Mac, turn on iCal and AddressBook syncing to Google or, if you prefer a more powerful option with more configurability, get a copy of Spanning Sync or go with Soocial, or some other service. These do good jobs of preventing dupes, etc.
5. Set your iPhone or iPad to use an Exchange server for contact and calendar syncing. (I still prefer to use a Google server for mail, it works better).
There you go. You should be mostly in the same place as with iCloud, although there are a few limitations. For instance, Google doesn't support all the custom contact fields that iCloud supports. That hasn't had much of an impact on me, although it can bother some people. Other than that, I'd just have to say things aren't exactly quite as seamless as with iCloud... for instance, iCal integration with Google Calendar works great, but you can tell from the user interface that they weren't really made to work together from day one.
Hope that helps.
It would be great if Apple fixed their s___ but I don't expect it. They've been making some bad decisions this year... releasing Lion too early, the horrible new AddressBook design, the mess that was iTunes Match (I think it's fixed now but I'm not going to risk it). Seems to me Apple is becoming more political, and less focused on the old mantra of "it just works." Bah. It doesn't work anymore.