The first few Serial.print("A") will add only a little bit, because that just copies the data into the outgoing buffer.
However, when that buffer fills up, the print() call will block until there is enough space in the buffer, which is going to be a lot longer than just sending a single letter.
When you send one letter at 56700 bps at 8N1 serial format, that's 176 microseconds per letter.
Also, the AVR cannot "do one interrupt" while "doing another interrupt" -- the next interrupt will be queued until the first interrupt is complete.
Finally, it sounds as if you may be having a bad cable or interference of some sort. Is this using a Duemilanove or an Uno? (e g, is the serial receiver the PC, or the USB chip of the Arduino?)