Disconnect then reconnect? Cleaning all contact points? This is the fan that came with your CPU or motherboard? I'm confused, as fans usually come bundled with the CPU.
But yea, check your motherboard manual's schematic against how you have the header installed. If it was installed correctly I'd clear the CMOS in case some setting is incorrectly applied in the BIOS.