which max settings was used by you??
I have the same problem (export from max), the best result i got was with uncompressed .avi output.
But this is very hardware-intense, and i get a filesize from around 300mb for a 3 sec sequence.
but i didnt experiment very long, but with compressed .avi settings the theora output was with flicker on some areas on the screen.
what compressed setting works best, would be very interesting for me.