There have been lot of phones that claimed to run on Linux, and most of them failed to support and service the phones properly. Few very good examples are the Motorola series A760/A768i/A780, which were available in India. These phones have Linux running in it, but thats just the Kernel, rest everything is proprietary and cannot be played with. Its not easily possible to do anything beyond what you could do with a non-Linux phone.
The trend seems to change now, with Nokia taking the lead of releasing an Internet Tablet running on an open platform - development of new applications, installing and running them was also supported and this made this tablet look like a true open-source device (not a phone!). With Trolltech releasing the Greenphone, phones went a little closer to having open platforms. FIC (First International Computers) has recently announced a phone based on OpenMoKo - and OpenMoKo has contribution from Herald Welte, which makes me believe that this is going to be another true OpenSource mobile — all for $350 
I am Prasad Sunkari,
co-founder of