I think 'failed' is a bit harsh. Sure, the first release of the Newton had mediocre handwriting recognition, but the subsequent releases were actually quite good. The biggest problem with the Newton was it's price, which was a direct result of the fact that the hardware it contained was comperable to WinPDAs that were released *years* later. The cost (better than $1000 for later models) is really what killed it IMHO.
To compare:
A Palm Pilot (released in March 1996) used a Motorola 68328 processor at 16 Mhz, and had 128 KB (Pilot 1000) or 512 KB (Pilot 5000) built in memory, and a 160x160 display.
A Newton Message Pad 130 (released in March 1996) had a much more powerful 20MHz ARM processor, 4MB ROM, 2.5MB RAM, a 320x240 display, an IR port (not present in Palms until the Palm III, and a standard PCMCIA (Type 2) slot.
A year later, the Newton Message Pad 2000 was released with a 162MHz StrongARM processor, 8MB ROM, 5MB RAM, 480x320 grayscale display, IR port, and dual Type 2 PCMCIA slots.
At the same time, Palm released the Palm Pilot Professional which was essentially just a memory upgrade (512K or 1024K). (IIRC, you could actually buy a memory upgrade that turned your Palm Pilot into a Personal or Professional, but that may have been the Personal or Professional into a III.)
As you can see, the Newton hardware was seriously impressive in its day, and by the time of the MessagePad 2000, the handwriting recognition was pretty darn good. Palm had slightly better accuracy, but achieved that by training the user to write in a specially designed alphabet called "Graffiti", where the Newton trained itself to recognize your normal handwriting.
Note: I'm not an expert on the Newton, I just think they got killed just as they were about to become feasable in affordable hardware.
