I happily moved from my Treo 300/600/650 PalmOS devices (never went to the WM version) to a BlackBerry Curve, and now a Bold 9650. Not having the touchscreen was odd (fixed later this year, or with a Torch), but I similarly needed a keyboard and the usability features of the BB OS made me very happy. BB's are well-known for their keyboard.
If you're looking at pre-owned, I'd be sure to get one running OS6 or capable of being upgraded to it.