Have you overclocked your CPU any and what temperature is that (case or internal)? It's a little hot when loaded but it's not overheating. My E6400 which is running stock everything, heatsink included, usually idles around 30 (case temp, core1/2 are ~40). It could also be that you do not have good airflow in your case and adding a fan in the right place is all you need to do.
Nope, I havne't OC'ed my CPU at all, it's all at stock.
I have 2 80mm fans on the side, 1 80mm on the back and another 80mm on the front of the case... The temps have gone up since I got my new GPU, I guess the heat could rising up off that?
Unless it has a 2 slot cooler it will cause the temps to go up. A new cooler wouldn't hurt but other than being on the slightly hot side your temps are still OK