It's actually quite common to find Linux-based smartphone nowadays, Linux has quite a large market share in the developing world including the crucial Indian and Chinese markets. Its main problem seems to be the splintering of different platforms that run on top of Linux, which is holding it back somewhat. Even Linux platforms that are nominally the same can often be binary incompatible.
Nokia themselves are dabbling in Linux, but so far their use of the OS has been entirely restricted to non-phone devices, the N800 and 770 internet tablets. As the tablets have no telephony abilities, they cannot be counted as smartphones, and they run a completely new user interface called Maemo (which can also be run on desktop Linux machines).