Hmmm... My Skt.478 3GHz Prescott ran @ 63Â°C full load when at stock speeds with the stock Intel cooler and stock thermal pad... 67Â°C with after-market cooling sounds very wrong indeed... I would suggest you double check how your CPU cooler is seated and make sure it is flush with the CPU IHS with nothing keeping it (even slightly) away from the IHS face. If you're not already using AS5 I would also recommend that as well, it reduced my temps by 3Â°C initially and 5Â°C after it cured.
Also, if you don't have one already, make sure to cut a hole in your case side panel right next to your CPU cooler's fan and mount a fan in the hole so it can feed your CPU cooler with cool air from outside the case. Doing this with my case (when I used air cooling) dropped my temps by 3Â°C at full load.
If you're looking into getting another CPU air cooler, you may want to have a look at the Thermalright XP-90, with the nickel-plated copper base. I found that this cooler could keep my pressy at 68Â°C full load when @ 4GHz with 10% extra v-core, which is pretty damn good for air cooling imo.
If all else fails, go for a nice entry level water cooling kit. My BigWaterSE keeps my 3GHz Pressy @ 63Â°C full load when running at 4GHz with 7.5% extra v-core. The prescott core CPU (or at least mine anyway) has a throttling temp of 73Â°C and a shut-down temp of 76Â°C, so anything below 65Â°C or so (full load) is perfectly acceptable in most cases.