Software serial @ 20MHz

I've noticed that my software serial is spotty at best. Lots of trash here and there. My Arduino clone is a Seeeduino and is running a 20 MHz. I know this affect timing for critical things like serial IO.

Is there a work around? Do i need to re-burn the bootloader?