Noisy data line clears up on wiring up multiple output pins of uC to Logic Analyzer
Clearly the inductance and capacitance of the lines changes when you plug/unplug your debugging lines. 

I would bet that if you moved your design from the breadboard to a printed circuit board where the inductance and capacitance (which would imply engineering the length and width of the traces) were engineered, you would see much better results.

With your breadboard have you looked for crosstalk and ringing on the lines?