Sadly, Arduino is not capable of high speed serial -- by that I mean 115200 or even 57.6k baud.
Most Arduino boards have a 16MHz crystal, which does not mesh well with the common baud rates above 19.2K, causing frequent dropped/garbage characters. It actually doesn't mesh very well with any common baud rate, but it's worst above 38.4K. It's a horrible choice of clock speeds.
My Dynon EFIS transmits data only at 115.2K, and I would love to do something with that data...what to do? The ATMEGA chip at the core of Arduino can do it, but that crystal is all wrong. From the ATMEGA168 data sheet:
This 2-3% error is enough for you to get a handful of characters through ok, but after that you'll start getting garbage.
Fortunately, there is a pretty easy solution. You can go to an electronics store, or go online, and purchase a 11.0592Mhz crystal (with 20pF load capacitance -- part X1103-ND from Digikey works). This is a special "UART crystal" whose frequency is exactly what you need for these higher baud rates. Observe:
If you're feeling brave you can de-solder the crystal from an existing Arduino board, or buy a seperate standalone board and install the slower crystal instead.
(If you're concerned about the slower processing speed at 11MHz, there is also another good UART frequency at 18-MHz-and-change, but to use it you are supposed to set the ATMEGA fuses to run the clock at a higher power setting, leading to reduced battery life. I didn't find that setting to be necessary, but your mileage may vary.)
The other piece of the equation is that you need to inform the software you'll be running of the different clock speed, otherwise all your timing (including the serial operations you're trying to get working) will be way off.
To do this, you'll need a machine capable of running Makefiles and gcc. That means downloading Xcode if you're on a mac, or cygwin on Widnows. Linux boxes can just install Make/gcc packages if not installed already.
Then go here to get a standalone Makefile for arduino programs:
Put your .pde program in the same directory of the Makefile, then follow the directions in the Makefile to get it set up. Lastly, modify the F_CPU line in the Makefile to the new clock speed (11059200). Note that you need to "make clean" anytime you change the clock speed so that everything gets rebuilt with the new constant. Then "make" to build and "make upload" to upload to the board.
When combined with an MC1489 receiver and a Protoduino board, the result is a multi-LED bar-graph that speaks flawlessly at 115.2Kbps: