The USART is driven by its own internal clock dividers. With the wide range of frequencies available for the processor clock, you can imagine that some will divide more evenly than others. Unfortunately, for your first kick at this particular cat, you chose poorly. 115,200 and 230,400 are perhaps the two worst freqs in terms of error (followed by 57,600) for a 16MHz clock. They'd be perfect if your clock was 14.7456MHz or 18.432MHz, but such is not the case.
Your best all-round choice at any freq is 38,400. At 16MHz, 76,800 is also good. Surprisingly, the best performer at what we would consider to be conventional freqs (8, 16 and 20MHz) is 250,000. Bear in mind that when the speed increases, the margin for error narrows. If the on-board oscillator is not functioning within spec you can throw all your calculations out the window.
All is not necessarily lost though. Auto baud detecting functions actually time the incoming signals and adjust themselves accordingly. When you do your UBRR calculation, you are in fact creating an output compare register value for the USART timer/counter. The calculation for 38,400 works out to be 51 (which is actually 52 when you count from zero) which you'll note is simply the period, in microseconds. Without doing the UBRR calculation, you can assign values directly to UBRR0 (49, 50, 51, 52, ...) thereby tweaking the baud rate until you find a match. Better though, that you stick to the low error rates if your design allows for it.
It does not appear to be a problem with the clock speed, it is a problem with the BAUD rate. I downloaded OP's code, made the obligatory changes to correct the syntax and got the same garbage (s)he complained of. Changing away from 115K (and 230) got rid of the problem.
DKWatson:
It does not appear to be a problem with the clock speed, it is a problem with the BAUD rate. I downloaded OP's code, made the obligatory changes to correct the syntax and got the same garbage (s)he complained of. Changing away from 115K (and 230) got rid of the problem.
What baud rate did you use and what was the corresponding UBRR value? Did you change any of the UCSR0A/B/C registers from what I originally had?