I completely agree on recommending the Nokia 6310i.
I've owned one for over two years now, and the main thing that have pi$$ed me off about it are an odd quirk how it resets all by itself occasionally - without warning, usually when replying to an sms text message. It just plain "reboots" or freezes up completely. The limited custom dictionary is a pain too.
Besides these, it's been a great multi-band, use anywhere phone.
My next quest is to decide on buying either an I-mate Jem or the full-sized I-Mate...
Cheers,
Ray Darr