Solution:
Under "Settings > Mail, Contacts, Calendar > Accounts" delete the account which is Exchange enabled. For me I use Exchange sync with Gmail. So I recreated the account,
http://www.google.com/support/mobile/bin/answer.py?hl=en&answer=138740.
My contacts now have the edit button back again. I seem to have lost the contacts that I loaded since the error appeared.
Background:
Under "Settings > Mail, Contacts, Calendar > Accounts"
I could see I have 7 email accounts. There was only 1 Exchange enabled email account (because it was previous OS3). Mail:ON, Contacts:OFF, Calendars:ON
I dont normally sync CONTACTS this way, because I prefer Groups / SyncInABlink to manage duplicates.
The following did not work:
(1) Turn Contacts:ON, check email (which should cause a sync)
(2) Connect iPhone to PC. Launch iTunes, click on iPhone, click on Info tab, tick [sync Contacts with Google Contacts], Apply
Got warning "The info on this iPhone is synced with another user account, delete or merge?" I selected merge. I got an error message: An error occurred while merging.
(3) Third thing I tried worked (see top for solution)