Why can't I add or edit contacts on my new iPhone 4? 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.
You can use the Contacts application provided in the iPhone 4, and create/edit contacts in there.