If it only happens when the fan comes on, it suggests two things to me.
Either your video card is getting too hot, and the fan isnt kicking on until the heat is causing problems.........
Or you have too much stuff running and your power supply cant hack it, and that fan is just the straw that broke the camel's back.
You said it ran fine before? Have you added any hardware since then? Anything that would use power? Check the fan power connection and make sure it is seated properly, not partway off showing any bare metal on the connections that could be grounding somewhere.
What kind of temps are you seeing on the video side? If you dont have any way to tell, try downloading an app that will watch the temps for you.
One last thought, also heat related. In your BIOS setup, is there a setting called "Thermal Throttling"? If you ARE running hot, and this setting is turned up, it will cut cycles on the CPU to compensate until the temps drop. That effectively cuts your CPU's clock cycles by whatever % that setting is on. At 50%, it will cut your CPU clock in half, skipping every other cycle.