If there's any doubt about the size of the gap that Apple has to close in terms of mindshare for its new iPhone, check out this graph which compares the "searchshare" of Nokia with the iPhone (and a couple of control phrases thrown in for good measure).
At any given time, people are using Google Search to look for "Nokia" almost twice as much as they look for "iPod". "iPhone", "Windows Mobile" and "Smartphone" all barely make a showing on this chart.
In other words, in order for the iPhone to have half as much searchshare as Nokia, it needs to be at least, or more popular (in terms of search queries) as the iPod.
The other interesting aspect of the chart is the relative decline of the popularity of term "iPod" since the end of 2005. Will this slide continue?