Thanks, guys. I really appreciate the input.
I'm using every single available pin of the Arduino, so using a different pin is not an option.
As soon as I add the initialise of the MIDI library (I do it in the order such that the 16x2 is initialised last) the 16x2 corrupts and remains corrupted. If I don't init the MIDI library, and only use MIDI over USB, then everything works fine. Although this proves the source of the problem, not using 5-pin MIDI is not an option.
I am considering looking at an option for reducing the number of pins I need to support the 16x2, but that's not ideal - I will have to completely redesign my circuitry and enclosure.