You were right, I looked at the datasheet a little, and it has the following to say regarding the ADC Noise Reduction mode:
"Apart from the ADC Conversion Complete interrupt, only an external reset, a Watchdog System Reset, a Watchdog Interrupt, a Brown-out reset, a 2-wire Serial Interface address match, a Timer/Counter2 interrupt an SPM/EEPROM ready interrupt, and external level interrupt on INT0 or INT1 pin change interrupt can wake up the MCU from ADC Noise Recution mode."
I figure you could either design your serial protocol to use some simple acknowledgment of transmitted messages, so in case your system was sleeping while a message arrived the host would retransmit it after a short while and your system could process it when it awakened from sleep.
Or you could use the external interrupt pin as an input, connected to the serial receive line (on the TTL side) and use it to sense whenever a start bit was detected. You'd probably want some sort of simple low-pass filter to improve noise immunity a bit though.
Another solution altogether would be an external ADC conversion chip I guess, that way your system could always remain responsive no matter what the ADC-chip is doing. Or you could switch communications over to an external chip on the SPI bus, which DOES work during ADC sleep mode. I've recently gotten some Maxim 3420 samples, which is a complete full-speed USB controller that talks to an MCU using SPI, and they're pretty cheap I think. But that's USB, which is kind of a hassle.
Oh, thanks for the points by the way! Now I can download that manual I wanted from the oscilloscope forum!