As you can see on Brainstorm, there is need for some kind of introduction of a new user to Ubuntu. On the one hand, this should include everything from setting up one's system to using each single app. On the other hand, this should in no way annoy experienced users, while probably helping them out if they need it.
Other requirements are internationalisation (translation into the user's language), friendliness and ease to use. This could be enhanced by reacting to the user's system (i.e. which apps are installed and how are they configured) and the user's actions (f.e. which programs are running, which one is active), but this is not needed for basic functionality.
Gnome already has a help system that can be found in "System -> Help". But in no way is it complete or even truly helpful.
Instead, I propose a "Ubuntu Assistant" which, when clicked, shows helpful messages. These range from common problems and their solution (like installing ndiswrapper, extra codecs) to general introductions (f.e. the Linux directory structure, the sudo concept), links to articles and howtos on the internet, and even the manpages and the app's own help.
On first start, the assistant pops up an introduction and explanation of this help system, also mentioning how it can be uninstalled. An experienced user can now disable the assistant (f.e. by uninstalling it) while a new user has a place where he/she can find help if needed.
After this message, the assistant does not pop up by its own, but only when clicked and then it shows helpful tips, if possible based on what programs are running. Example: A new user has just opened Evolution. He doesn't know how to use it, so he opens the assistant. He can read now follow links to articles about Email, Evolution, Cryptography etc.
If the assistant can detect which packages are installed, the included articles could also inform the user if he has to install new packages (if they aren't installed) or direct him to the correct app. Example: The user reads about Emailing, and because Thunderbird is installed and Evolution is not, the assistant directs him to the Thunderbird help.
Also, the assistant should feature a search for all the questions the user has that are independent of the running apps.
For a concrete implementation I'd suggest an applet much like Wanda the fish. The look of the assistant should be changeable, I'd suggest a cute, animated penguin for default, but also a professional looking one like a non-animated question mark should be included. The messages are shown in a pop up directly under/above the applet.
Yes, this sounds a lot like Microsoft's Clippy which is quite notorious, but the concept itself is quite good. The major annoyance of Clippy was that it'd pop up on its own with ridiculous suggestions. By only popping up when clicked, this idea avoids this. Instead Ubuntu had a very friendly help system with something like a "personality" (an animal) thus talking to the user on a direct and personal level instead of a professional, distanced and clean help system (like every one I have seen so far). By reacting to the system and user actions the help is even more useful.