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")

This is a screenshot of the Cisco IP Communicator software. You can use it to make phone calls on your computer over the internet, which is cool because it uses your office extension so you can work from anywhere without having to tell your work friends to call a different number.
It is also a great example of software whose UI uses a metaphor — a term I’ll apply to interfaces that are designed to evoke a familiar non-software object to encourage ease of use. CIPC looks and behaves exactly like the physical phone sitting on your desk, so you can use it without having to learn anything new.
Recognizable metaphors are attractive to UI designers, but metaphors often do more harm than good:
Most metaphors are incomplete – software generally doesn't exactly mirror the object its interface is based on – and it's hard for users to understand how software will function when the metaphor fails. For example, even after you empty the "trash can" in OS X, your files are still recoverable, even though the trash can metaphor suggests they are gone forever (or at least inaccessible).
(And More Importantly) Metaphors are often based on objects that would have been designed differently if the capabilities of a computer were available to them.
CIPC is a great example of this. The designers of the OG phone would have done things differently had they full keyboards, high resolution screens, and copious processing power available to them. Why should computer software mimic items that were designed the way they were because they couldn't take advantage of a computer? In the CIPC case, for example, all I want is an autocompleting text box into which I can enter the name of the person I want to call.
CIPC is a great example of this. The designers of the OG phone would have done things differently had they full keyboards, high resolution screens, and copious processing power available to them. Why should computer software mimic items that were designed the way they were because they couldn’t take advantage of a computer? In the CIPC case, for example, all I want is an autocompleting text box into which I can enter the name of the person I want to call.
The trash can I mentioned in (1) is also relevant for (2). Why should I have to “move” something to delete it? Pressing “delete” should cause the file to disappear, viewable (in its original directory) if I do something like View » Show Deleted Items.
For that matter, why should there be any concept of “emptying the trash” i.e., (per the metaphor) “deleting files forever”? When you “empty the trash”, what’s actually going on is the operating system designates those files “safe to write over with other data”. However, the operating system should be smart enough not to write over any of these “deleted” files until it has to. In the case of a 50Kb Word document on a 1000GB hard drive, this should be virtually never.
There’s no good trash can-like metaphor for a filesystem that saves every version of every document, and maybe this makes such a system harder for a beginner to understand; but the benefits it would offer to intermediate and advanced users would more than compensate.
Another good example of this is the filing cabinet / folder metaphor for organizing files. (As a side point, this metaphor isn’t even that strong — no physical filing cabinet has folders nested 10 levels deep, and the fact that you can do this on a computer is confusing to beginners). In a physical filing cabinet, a document can only be in one folder. However, on a computer, a single “file” can be “placed” in any number of “folders”. Why can’t I describe “Annual Report.doc” as both Categories » Work » Reports » Annual Report.doc and Time » 2008 » December » Annual Report.doc? (Google Docs is moving in this direction — it’s about time).
Many forms use radio buttons or dropdown menus under the theory that users are more comfortable “picking from lists” rather than just entering data off the top of their heads. Most of the time though, especially when users are confident in their answers, it’s just easier to let them type the answers directly rather than requiring users to shift hand positions several times while entering a small amount of data.
Dropdown menus are particularly useless. They are useful when users have to pick from a list of values, but it’s almost always easier to pick values from an autocompleting list than scan (and possibly scroll) down a dropdown:

Dropdowns are easier to navigate when there are fewer options, but in this case radio buttons are often even better. If you must have a dropdown, at least give users the ability enter values with the keyboard in addition to choosing from a list.
Why do I have to enter my city, state, and zipcode whenever I want something delivered? City and state are derivable from zipcode! Mint.com is one of the only websites that gets this right:

Also notice that Mint validates your entry automatically without your having to press submit. Once a form is submitted, the only way it can notify users about problems is to reload the page. But when the page gets reloaded like this, users don’t know what state their data is in. Can they just correct the one error? Or do they have to re-enter other information that was previously entered correctly. Many websites clear password fields in this case, some do not.
The reason to force users to fill out a form is to gather explicitly structured data — you want to know that this part is the city, this other part is the zipcode, etc. However, it’s not always necessary to force users to explicitly structure the data they enter; often it’s possible to parse their plain text entry and guess at the structure. (This is particularly effective when it’s easy for users to correct errors).
For example, imagine if Google Maps used a conventional form to ask you for an address:

Google Maps doesn’t ask you to structure your input because it’s possible to guess what you mean by looking at an unstructured string of text. There’s no reason that online vendors couldn’t use this same strategy.
Here is my ideal address entry “form”:

You enter any string in the address box that unambiguously identifies your location. The map and postal address below update automatically so you can see if what you’ve entered is incorrect.