One of the frequent problems that new Linux users have is trying to install Windows .exe files, instead of using Add/Remove or a .deb to install software.  An easy way to fix this would be to prominently show the Add/Remove programs dialog after a fresh install (without a pop-up).

Even if you think that SSDs (solid state drives) will get better and this will eventually be unnecessary, a custom mode to minimize writes for SSDs would give Linux a real boost, at least in the short term, as SSDs become more and more popular, especially in netbooks.

Particularly with updates and software installations, it is a pain to have to wait for one thing to finish before starting the next. The simple solution to this would be to have a queue for tasks that cannot be preformed until the last one is finished, so I can tell my computer to perform an update and then install some application, and I can walk away.

Many computers are used by a number of different people, so providing an easy way of setting up multiple user accounts from the beginning would be useful.