First of all, remember that sync works both ways - if you delete contacts on the phone, it will delete them on google. If this happens, don't despair, as gmail has a nice "way-back" type of restore; you can restore back to any time. I used this for my wife's iphone when I set it up.
I mainly wanted to post this for the above CYA, as I think it's important. I don't remember exactly what settings I had to change to get it working, and she's not around now, so I can't look to see. But knowing about the restore should give you the ability to experiment more.
I may have set up the sync to their icloud, or whatever it's called, but I doubt that this really buys anything. I believe that once you get it in sync, so to speak, it will work correctly after that. I think you just need to restore the gmail contacts, and they will then sync to the phone. It may have tried to sync gmail to the phone before instead of the other way around previously.
Sorry I can't give the exact settings or procedure to use, but I hope it will help.