Actually, listening to this conversation it's completely clear that he'd been imagining a device like the iPhone even then. It clearly solves a problem he has. Remember when he introduced the iPhone as "three revolutionary new products"? There were two that people really wanted: A touch screen iPod. A phone. And one that got lukewarm reception because people didn't know what to make of it: An breakthrough internet communicator. The iPhone was always about the third part for Steve, but you need the other two to sell it to the public.
As for your glib comment about a keyboard, I find the iPhone keyboard is wonderful for typing on. Yes, it's software, but it is a keyboard.
He was pretty specifically talking about the Newton, which produced either decently captured raster handwriting or questionably recognized plain text. You don't want to be the one telling people to use a device in a way which is best described as questionable. The iPhone produces reasonably keyed plain text, or questionably smudged handwriting. Since adding cellular modems to handheld devices was straightforward engineering at the time, that inversion of input is probably what made the iPhone take another five years of work when they returned to the idea after stabilizing OS X.
You know, I might have to dig out my MessagePad 2000 to check, but I'm not all that certain I get better recognition on my iPhone than I did on that. I frequently have to go back and correct words on the iPhone, too (usually because my 3G iPhone is laggy or I'm using words like "laggy" that aren't in the dictionary.)
