Does it work better if you use Serial.begin(57599) or other numbers around 57600? This should trick the 328 and 8u2 into using the same parameters.
I am not having any problems with 57600 baud myself but I had a similar issue with 300 baud. I had to use Serial.begin(298) to get that speed to work.
I am using an Arduino Uno on Ubuntu 10.10 64 bit and Windows XP. An older (FTDI) Arduino Mega works fine at 300 baud on both systems.