The Newton 2000/2100 was very good with handwriting recognition. The earlier models were slow and used a different recognition system.I believe the last great handwriting/stylus based system, Palm OS, showed that the public could really care less about handwriting recognition. Perhaps learning the strokes of Graffiti was too much, but even those that did (like me) didn't clamor for it's return when provided a keyboard.
I would venture to say that if the Newton 2100 was the first Newton model released, the Newton would have been a big success. Unfortunately, the Newton platform could not eliminate the stigma associated with the handwriting recognition, or lack thereof, that the earlier models were capable of doing.
Graffiti is not normal. It required the user to learn a new writing language via the Graffiti pen strokes. Sure character recognition improved as long as you followed the Graffiti rules.
The beauty of the Newton is that it recognized "your" handwriting. With the 2100 I was able to input text rather quickly -- almost as fast as typing. And if you were in a big hurry, you could tell it to wait to interpret your input until after you wrote everything down.
If Apple introduced an improved version of the handwriting recognition that the 2100 used over 10 years ago, it would be awesome -- especially on a 10.4 inch screen. IMHO, the iPhone and touch are too small for pen input. But on a 10.4 inch screen, there is so much that you could do with a pen.