As of IDE 1.0, the serial buffer should be non-blocking. However, the amount of data you can buffer is likely limited. My guess is that the ADC is waiting for the Serial transmission to finish.
The only true "multitasking" that the Arduino is capable of is running the ADC independently from the main CPU (at least as far as I'm aware of). Everything else interrupts the flow of the CPU as it diverts it's attention to an ISR, serial comm that is longer than 8 bytes, or other distraction.
As others have suggested, try minimizing the impact of the serial operations by reducing the amount of data you need to send. For example, in my power logger, I would sample two channels and while the output from channel A was being processed, I would be sampling Channel B, and vice-versa. That minimized the time required later to do final data processing and each data transmission consisted of maybe 20-odd bytes. FWIW, I used no pre-scaler adjustement to maintain the quasi-10bit resolution and still got several thousand samples per channel every second.
So I too would suggest sending small squirts of data but I would also try sending them at higher speeds. I successfully interfaced two Arduinos at 1Mbit/s per the Atmel dataspec. You can't use those speeds in the IDE, however (for, IMO, bad legacy reasons) so use Putty or any other terminal instead.