Quick Fix
I was having this same problem and here is what worked for me.
Open address book on mac computer. Create new contacts group called temp. Add all your contacts to this group. Wait until the group pushes to mobile me cloud. When you check it on me.com, all your contacts should appear in the new group you created. Once they are on me.com you can go back to the address book on your mac and delete the temp group. All of your contacts should stay in your cloud after this and should push normally.