First, a few questions:
Is that at idle, loaded, or fully loaded? What are you using to measure the temperature? Which measure are you reporting? What type of case do you have? Motherboard? What is your ambient (room) temperature?
It seems likely the heatsink/fan may not be seated all the way. But until we know more about your setup that's just a guess.
You said "the board is reporting" - if you're reading that from the motherboard's BIOS you can get more accurate real-use readings from good software once you're in the OS. (Although 58C from the BIOS would be very high.) Pick a couple programs at first until you're comfortable with one and know you're getting accurate readings. Good choices are: SpeedFan, RealTemp, CoreTemp. I don't have links on hand but I'm sure you can find them elsewhere in these forums/google or perhaps someone else can help provide download links.