If the heatsinks are hot, the thermal paste is working fine as the heat is moving from the chips to the heatsinks. They need more airflow.
The heatsinks are designed to take airflow from a top-down cooler, such as the stock one. Since your cooler is the "tower" style, you are getting little to no airflow over the motherboard. A well placed fan should take care of this.