Debugging when oscilloscope grounds cures the problem
There are three main possibilities --  


there is some external system you're connecting to, and you haven't
passed a reference voltage between your circuit and this system.  If
the external system is connected to earth ground, when you attach
the ground of your scope cable to your circuit, you are now passing
a reference and fixing the problem. (my first bet if I were a betting man).
Something wants a little more capacitance and the scope probe is providing it
Some spurious currents are looking for a better path to ground, and the earth ground is providing it.


The first option is probably debuggable by extension, the second by adding caps as others have described.  The third might be caused by currents associated with voltage spikes associated with PWM control of a motor, and missing the diode you need to deal with this.  You might consider just replacing the fan with a few resistors (i.e., a non-inductive load) in parallel (sufficient number to deal with the power generated) and see if the problems go away.

One more issue--  You may just have your power wired up incorrectly.  If GND in your circuit is chassis ground (i.e., the "Ground" jack on your power supply), and there is no internal connection between V- and ground on the supply, you need to make a connection between chassis ground and V- or there is no reference to V+, or, instead of hooking your circuit ground to chassis ground, you use V- for GND in your circuit.