The metal things that make the connection have barbs on their sides. You will need to compress the barbs with a needle-nose plier or something, so you can slide the metal thing out of the plastic plug.
I'm not positive what you meant about how you have it hooked up now. On a typical computer wiring harness, the black wires are ground, red is +5V and yellow is +12. If you have your fan hooked up to a black and a red wire from your power supply, it should be turning slowly, since that would be only 5 volts, and most (though not all) internal fans are 12V fans.