How fast can arduino process (interrupts)?

I'm working on a robot right now and I'm trying to use the arduino to read the quadrature encoders on the motors. I am able to read the encoders and increment a counter successfully at low speeds, but as the speed increases I run into problems. Namely with serial communications. It seems that if the motors turn too fast it interrupts the serial during a TX or RX causing the connection to crash. The arduino keeps running it's program as intended. This isn't terrible, I just don't print to serial while the bot is moving. My concern is this, if I'm already having problems like this, at what point will I definitely be unable to use the arduino? (if at all)

Here are the specs:
640 counts/rev (only reading half, so 320)
180rpm output shaft speed
52:1 gear ratio
If my math is right this comes out to 960Hz/channel, 1920Hz total.
That means an interrupt potentially every 0.5ms. 16Mhz is a lot faster than this, but many things take several cycles to complete.

I'll be doing a fair amount of other math while the motors are running (pid speed control, navigating to waypoints, etc) which I know will have a big effect.

So am I crazy for trying this, or am I drastically underestimating the little Atmega168?

at 0.5ms the interrupt speed is not a issue,
I have done a soft serial at 9600 baud with having a interrupt at every bit (0.1ms) and also a DMX console with baud rate 250K, interrupt at every char (0.004ms)
if you don't need to do all the math all the time you could divide the encoder, let say at each 4 interrupt, i will do the job. that could also save you some time. (counting to 4 does not take that much) or even, at 1 i do the P of the PID at 2 i do the "i" of the PID at 3 ... you get the idea?