Ae we talking in F or C? That makes a difference. My Q6600 runs at about 30-34c depending on ambient and then 50c under full load.
I would probably check your heatsink as it may not be sitting properly. As well make sure you used fresh thermal paste as that can cause issues since old paste will be dry and not conduct heat well or leave a large amount of air bubbles which also prevent heat from conducting to the cooler properly.