Is your Gmail account set up as Exchange?
EDIT: just tested this myself and here's how it works (Gmail set up as Exchange): go into the Contacts.app and tap on "Groups" in the upper left corner, then locate your Gmail account and tap on "Contacts", then tap on the + and then add in your contact. You should be able to see it in your Gmail account within a minute or so.