Cannot remove 4 pin fan connector

Solution
Try pressing on the bulging parts of the molex plug form the PSU. Press on the bulges, as they are designed for the "quick release" of molex.
Agreed. Then if that is not sufficient, get a straight-blade screwdriver with a relatively wide blade. Position the blade between the two connectors where there are stuck-out flanges (the edges look good for this), so that you can twist the screwdriver and force the two halves apart. You may have to alternate between the two edges to move it a little bit at a time each side. While doing this, squeeze the soft bulging part of the black connector half as Ryan_78 said. That should start it to loosen up.