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.
i7 860 | Gigabyte GA-P55M-UD2 | CM Hyper 212+ | 4GB G.Skill Ripjaws 1600 CAS9 (F3-12800CL9D-4GBRL) | Radeon HD 4670 (Gigabyte GV-R467ZL-1GI) | Corsair CMPSU-450VX | WD Caviar Black 640GB | Seagate LP 1TB | Sony Optiarc Black 24x | CM Elite 310 (RC-310-BWN1-GP) + 120mm front intake | Dell UltraSharp 2208WFP (1680x1050) | Windows 7 Pro x64