Is it really a bad idea to leave an MCU input pin floating?

Problem:
Leaving a pin configured as an input floating is dangerous simply because you cannot be sure of the state of the pin. Like you mentioned, because of your circuit, your pin was sometimes LOW or sometimes in no-man's land or could sometimes go to HIGH.

Result:
Essentially, the floating input WILL definitely cause erratic chip operation or unpredictable behaviour. I have noticed some chips froze by simply moving my hand closer to the board (I wasn't wearing a ESD wrist band) or some would have different startup behaviour each time the board would powerup.

Why:
This happens simply because if there is external noise on that pin, the pin would oscillate, which would drain power as CMOS logic gates drain power when they switch states.

Solution:
Most micros nowdays have internal pullups as well, so that could prevent this behaviour from occuring. Another option would be to configure the pin as an output so it does not affect the internals.

It's a little worse than just being in an unknown state, or toggling needlessly. Digital circuits nowadays are mostly of CMOS type, with transistors switching both high and low sides; when we have clear 1s and 0s, they are either off or saturated, the two most efficient states for the transistors to be in. In between, however, is a region of linear operation; it's used for analog amplifiers, but it is not as efficient as the extremes - meaning more power is wasted as heat in the transistor. In the worst case, both the high and low side transistors leak thus (because the pin is in fact neither high nor low), and they can then combine to cause a notable current within the chip as they try to drive the internal state both high and low - possibly doing the same to the next gate in a chain reaction. The heat could become a problem even if the power isn't. IntelliChick's solutions still apply.

For pins also connected to ADCs, some microcontrollers offer the function to disable the digital input buffer, to prevent both this problem and leakage distorting the signal.

In practice the main effect is increased power consumption. If a pin is actually floating as opposed to connected to some indeterminate voltage source, it is possible for oscillation to occur, which as well as increasing power draw may introduce noise into other parts of the system. Any pin which has the ability to be used for an ADC or comparator input will have the facility to disconnect the digital input buffer to avoid this problem. (DIDR on AVR, ADCON1/ANSEL on PIC)