Sounds about right. Normal idle temps on those CPUs are about 33-36C max if I recall correctly.
Best bet Christina is to simply power down, remove the HSF, remove any thermal paste, and redo it from scratch: new thermal paste, spread it properly, remount the HSF, check that everthing is tight and seated flat, etc. Then power up, go directly into BIOS and into PC Health (or something like that). Watch the CPU temps, let the computer run for 20 minutes and see what happens.
Report back with your results.