First, take a look at Edward Tufte’s bomb video:
Here are some of my own complaints:
You have to set your "Favorite" contacts manually (the phone should pick automatically from your most recently called / emailed contacts)
Update: This is false – my bad. You can't change the order of your "Favorite" contacts (each contact is ordered based on when it was added to favorites – this is pretty insane)
When you look at your contacts within the interface for making a call, contacts without phone numbers should be filtered out
The interface for accepting / canceling an auto-correct suggestion is impossibly small:
Furthermore, the iPhone's auto-correction dictionary is a tad formal (e.g., it doesn't include "yo"). (To apple's credit though, the dictionary does include the names of your contacts)
The weather icon on the main screen doesn't update with the current weather (it always says 73 degrees). (This sort of thing is definitely possible; e.g., the calendar icon always updates to show the current date)
If you want to compose a text message while out of service and send it as soon as service resumes, you have to do it manually (there's no "SMS Outbox")