Sony Ericsson K850
I've had the K800i for about a year and LOVE IT to death. REALLY easy to text, the T9 is VERY intuitive, will even suggest the next word. I've had a little frustration with numbers while texting, but not a big deal. Operating systems more than makes up for it.
I made a "New Text" a short cut. The middle selector key has 4 programmable shortcuts and I set new txt as one of them so it is one-touch.
Having an internal battle myself between a K850 and a Nokia N95... totally torn.