Arduino serial communication protocol design
Is it possible that your problem is caused by Arduino? I know that sounds strange, because Arduino strongly relies on serial communication and it doesn't usually fail. But I would suggest you to try your Arduino with different speeds, dumping human readable data and monitoring with a terminal program. I've had the same problem and that was caused by ground problem of my arduino. Also, another solution might be using a custom arduino design with serial-friendly clock speeds like 14.7456MHz or any value multiples of 3.6864MHz. 
Hope it helps...