I assume you are using the standard Intel CPU cooler that came with your CPU? Your temperatures are rather high, the temperatures at idle when Speed Step has the CPU at 1600MHz could be much better. Changing the thermal paste won't help much at all, you need a better CPU cooler. Adding more fans to your PC's case will help too, but a better CPU cooler will probably help the most.
