I've never experienced resonator-introduced serial problems, even when communicating at 115.2 kbps (with a 20 MHz resonator). Unless you're using the internal oscillator, the dominant error in serial timing typically comes from your being unable to reach the exact frequency of the baud you want to use. For example, when using a perfect 16 MHz clock, the closest you can come to 115.2 kbps is 111.1 kbps (which results in an error of -3.5%). The next highest baud you can reach exactly is 125 kbps. In this situation, a 16 MHz crystal will not noticeably improve performance over a 16 MHz resonator.
Is it greater than double the worst case resonator error?
It's not if you use 6-bit bytes. Additionally, in my experience you can exceed the recommended maximum receiver error by a few tenths of a percent and still be just fine, which means that in the absolute worst case you're still ok (and also note just how unlikely the absolute worst case is given the requirement that all the various error sources in the equation all be a their extremes with the same sign on one AVR and all be at their extremes with the opposite sign on the other AVR).
Lastly, if your receiver error is slightly above the recommended maximum error, all this means is that over time you will lose synchronization with your target if you are transmitting as fast as the hardware can transmit with no breaks. This might happen after you have transmitted 50 bytes or 100 bytes. The solution is to simply insert a very small delay every x bytes so that the UARTs can resynchronize. The maximum receiver error is the error below which synchronization will never be lost even if you stream bytes non-stop forever.
- Ben