I was thinking this might be the issue. I guess I was confused about the pin mapping.
Does this imply that when the Arduino is trying to send serial data to the external shift register (through the LiquidCrystal library), it's also transmitting/listening on pins 0 and 1? The serial data sent through the USB does not seem to clash in the same way (i.e. Serial.print() statements do not cause conflicts -- that I've noticed at least).
I'll try and only use the interrupts on pins 2 and 3 and see what results I get.