I've updated AltSoftSerial with a new, faster pair of receive interrupts.
You may need to refresh the page to download it. The new zip file is 7553 bytes.http://www.pjrc.com/teensy/td_libs_AltSoftSerial.html
The original code stored the captured input edges to an array, then did all the analysis during the stop bit to recover the byte from the timing of the edges. Sadly, the AVR at 16 MHz just isn't fast enough to complete the analysis for bytes with a pattern of 0101010 before well into the next start bit. Sometimes if the LSB of the next byte was 1 (serial sends LSB first), the 2nd edge defining the LSB would occur before the interrupt could respond to the leading edge of the start bit, because the interrupt response was delayed by the analysis happening from the prior stop bit.
I redesigned the interrupt handlers. Now it does the analysis incrementally on each interrupt. I also made the edge detect interrupt able to put the detected byte into the buffer, so the timeout interrupt doesn't need to run. Of course, that only applies when the MSB is zero, so the stop bit begins with a rising edge. When the MSB is one, the stop bit is detected by the timeout interrupt instead. Previously the edge detect interrupt would put that final rising edge into the buffer, then the timeout interrupt would do the analysis. The AVR is terribly slow getting into and out of interrupt handlers, so never needing to run 2 interrupt routines per bit saves a lot of time. This test case didn't trigger that failure mode, but if bytes with the MSB set are received at 57600, they should now work and not corrupt subsequent bytes.
The stop bit interrupt now (hopefully) always completes before the edge of the next start bit, at 57600 baud. However, there's not a huge amount of timing margin, so any other interrupts or code adding more than about 9 us bit time interrupt latency can cause AltSoftSerial to receive incorrectly at 57600. Many interrupts are several us, so check that data carefully while you're doing other stuff generating interrupts.