Increase the baud rate. The risk is a higher incidence of corrupt data.Upgrade to a "bigger" board. Something with a processor from the ATmega1280 or ATmega644 family.
A higher baud rate equates to much less time spent in the interrupt service routine which reduces the chance of an overrun and the amount of overrun if one occurs. (I'm assuming @miclmr's diagnosis is correct.)