OP says the fan runs, so it IS plugged in. However, four other ideas to check:
1. The new heatsink included a pre-applied thermal paste. Many of these have a protective plastic film over that that you MUST remove before installing. Otherwise the heat removal is severely limited. Did you remove it?
2. IF your new fan is plugged into the mobo, make sure it is the CPU_FAN port, and not another.
3. IF your new fan is plugged into the CPU_FAN port, it is vaguely possible that, although it turns, the fan's speed signal is not getting back to the mobo port. Disconnect the fan from the port, inspect the connector and pins closely for bent or something else, then reconnect. MAYBE this will fix a poor connection problem on Pin #3.
4. Maybe your new fan does not plug into the mobo CPU_FAN port, and instead is connected directly to the PSU via a 4-pin Molex connector. Is that your situation? If so, your mobo is no longer receiving a fan speed signal. On many mobos, the BIOS checks this signal carefully and, if it receives none it believes the CPU cooling fan has failed. It then will shut down the system completely to prevent CPU overheating, without even waiting for the CPU temperature sensor to show actual overheating. IF this is your situation, you'll need to do two things. First is to fool your BIOS into thinking it has a good fan operation so you can get it to boot. To do that, temporarily attach any fan (your old one?) to the mobo CPU_FAN port and boot. Secondly, when you do this, go immediately into BIOS Setup and go to where the CPU fan is configured and monitored. If you're NOT running your CPU fan from the mobo port, you probably have to tell it to ignore the CPU Fan speed monitoring process so that it will not take action for "no CPU fan speed". Save and Exit to reboot, then you can disconnect the temporary fan. From now on it should work OK.