I've got a Gallatin that was running 54C idle with the stock HSF and paste. Got a Zalman 7000 with better paste, and idle immediately reduced to 30C, 42C under a full load. You might get better results if cleaning out the heatsink, but doubtful.
Arctic 5 should have helped more, so my guess is that there's no air flow in your case. Bunch up your IDE cables and tie them out of the way (or replace with rounded), and be smart about organizing the other cables. Keeping the airflow unobstructed to the CPU is important.
Make sure you have decent air intake, and that the vents aren't blocked by furniture or whatever. If underneath a cluttered desk with little room in the back, consider an intake fan for the front bezel.
Also consider the PSU and its location: it should be helping you to exhaust hot air in the case. Preferably, a dual-fan that sits above the CPU is best, but if it's a single-fan that sits beside the CPU, consider an exhaust fan at the top of the case.