On my new iPhone 4, I can add a new contact after talking to them (Add as new contact) but I cannot otherwise add new contacts, or edit existing ones.
It looks like a bug. Is there a way to work around it, or do I have to wait for Apple to fix their issue? The phone is not jailbroken.

