I think making sure your current cooler is seated properly would be the first step. If the cooler is still not keeping temps below 60C when reseated properly, then . . . it might be an IHS issue which means that upgrading your cooler might not work as well as desired. Adding a case fan probably won't help unless your system is absolutely starved for airflow.
In fact, I'd say check the IHS when reseating to find out if it's concave.
oh, and when you say you didn't put any thermal paste on the cpu, do you mean that you just used the thermal paste/pad that comes pre-applied to the stock HSF? Or are you talking bare metal-on-metal contact here? The stock thermal paste/pad should be adequate for running a stock speeds.