If your motherboard is immediately reporting such temperatures, you can bet the problem has to do with the CPU as you are reporting. In particular, it has to do with the CPU being unable to release it's heat efficiently. As others have stated, you may want to remove the heatsink, remove the old thermal paste and apply some new paste before reseating the heatsink.
Be sure to follow Intel's guidelines here
If the problem persists, try using a different heatsink (though I doubt the one you have is the problem). If the different heatsink still doesn't work, you can be sure your CPU is on the fritz.