Arduino Uno with UsbSerial Android library w/ baud rate over 9600?
I have no enough reputations to make a comment so I will drop my two cents here.

Are you changing the baudrate at both sides?

I have been using the arduino's built-in UART library for a while using different baudrates with no problems. Your problem could be an issue related to the library you are using.