While Intel's stock coolers are known for being less than ideal, they shouldn't be as bad as your describing.
You mentioned putting new paste on...
Did you clean the chip and heat sink before applying the paste? Did the stock heat sink have a TIM (Thermal Interface Material) pad on the base where it attaches to the IHS (Integrated Heat Spreader) of the CPU?
If you have both paste and a TIM between your CPU and heat sink, you may be insulating the connection rather than encouraging good heat transfer.
One assumes that since you only just applied the heat sink, the blades of the heat sink are free of obstructions such as dust.
Is the fan on the heat sink set to run at an unusually low setting, perhaps? Check your BIOS and set the fan higher if possible.