My iPhone downloads my contacts from gmail. Whenever I click on 'Add new contact' I want this new contact to be uploaded to gmail. Unfortunately that is not the default behaviour. The new contact goes to iCloud, even though my default mail and contacts account is gmail.
Here's how to fix this:
Remove the iCloud contacts sync. This will completely remove the iCloud contacts group:
Problem solved