David,
Because NewSoftSerial is a software-based serial port, it is sensitive to variations in clock speed, especially at higher baud rates, that the HW serial port is immune to. NSS's 57.6K RX mode is optimized for the 16MHz Arduino's I have, but it may be that your Arduino's clock varies enough to break this.
If you'd care to try and tune NewSoftSerial for your device, delete the NewSoftSerial.o file and modify _bitDelay (currently 31) in the begin() function, case 57600. Try 32 or 30 or 33 or 29 and see if this improves the situation.
On this subject, I have been toying with building an "auto-tune" test mode that would allow people in this situation to automatically customize NSS to their specific board's quirks. You would run a simple program on the host that blasts a repeating pattern to the Arduino. A sketch on the Arduino automatically varies _bitDelay until the recognized pattern is seen. Does this seem interesting?
Mikal