Yeah those are some really hot temperatures my man. Are you sure you seated your heatsink properly and put on the compound properly and all that good stuff? Did you change out JUST the fan or did you change out the heatsink too? If it was the stock heatsink did you make sure to safely remove the pre-existing thermal pad and not put grease on top of it. My Athlon 2400+ XP would run at 64C idle but that was when I had standard Heatsink and fan and NO case fans at all with the side panel open. Have you formatted the hard drive before you put the computer together so it's a nice fresh install with the right drivers, updates, etc??