SoftwareSerial does 115200?
I'd go with a chip that has 2 serial ports, like a 1284P with its 16K of SRAM for databuffering as well.
Here's a duemilanove sytle board that uses the 1284P chip.
PL here Cross Roads Electronics,
bare board $5 with shipping. parts can be had for $15-20, or you can scrounge your parts bin for a lot of it.