ICloud – Exchange contacts do not appear in iCloud

The data stores can get confused. It's usually a server issue but you seem to have narrowed that out by the details you posted.

Giving the iPhone a totally fresh database then re-establishing sync often helps when the databases are failing to sync correctly.

Since there is no way to just start over for contacts only, you have a short dance of steps.

1. Disable all contact syncing over the air.
2. Power cycle the phone
3. Use a test account (i make a new user account on my mac with an empty address book) - syncing from iTunes to overwrite all contacts stored on the phone clears the data store well. You can have iTunes only overwrite the contacts and not affect any other data on the iPhone.
4. Sync back to your main iTunes if desired, then finally re-enable contact sync over the air.

Since the contact database gets restored from a backup, restoring the phone won't cure contact database errors. If you can re-set up the phone, you could restore and set it up as a new device also.

Use iTunes to sync and make sure you have your phone contacts in your MS-Exchange folder. Then you can either use the Google Apps migration tool or export them from outlook and into gmail.

Next you can remove the exchange account (which will probably delete you contacts).

Next you can uncheck the box in itunes that says "sync my contacts" so that they will all come off of your phone. Make sure you have them backed up first.

You can also uncheck the box to tell it not to sync the calendar if you like.

Next, you can add a Gmail account or google apps account - but when you do, don't click on Gmail for the account type - choose "Exchange" because it allows syncing of contacts and calendars, too.

See the gmail site for more details:

http://www.google.com/support/mobile/bin/answer.py?answer=138740