It sounds as if the nearest clock divider ratio for 115200 baud when generated from 8MHz is out of range - this may be inevitable since the divider ratios get smaller for high baud rates. You could try non-standard baud rates at the PC end of the connection in case that helps (try increasing and decreasing in about 5% amounts).
Looking at the code in HardwareSerial.cpp suggests that only baudrates that divide 1,000,000 to yield an odd number are accurately represented, so perhaps try 200kbaud at both ends? For the 16MHz case substitute 2,000,000 - divide by 17 gives 117.6kbaud which is close to 115.2kbaud.