Do you have another ATMega chip to put in? Sounds like the timer for the UART is running at 2X.
Odd that both do it - any funny power glitches or anything occur, lightning nearby or anything?
The other thing you can try is looking at the fuse settings;http://www.geocities.jp/arduino_diecimila/bootloader/index_en.html
I have a duemilanove set up like this, with some pins installed at the X3 location so I put jumpers from there to the ICSP header and read the fuses like as described. Maybe knowing what they are set at will help. Or not.