Did you follow the instructions for syncing Address Book with MobileMe? Here's what I did in order:
1. Sync iPhone to Mac with iTunes so my Mac's address book -> iPhone.
2. Set up MobileMe account.
3. Sync Mac's address book to MobileMe.
4. Set up iPhone to sync with MobileMe.
The bulk of the syncing was done in step 1. After that, it's syncing the minor adjustments over the air with MobileMe.