I was having this same issue on my Galaxy S2 then I started messing around in the menus. From the contacts list I went to Menu -> More -> Settings. There I found a setting that says "Save new contacts to" and for me it was set to phone, so I changed it to gmail, issue resolved.
