Core 2 Duo Idle Temps

Ok, long story short:

In the Navy. Just did two deployments rather close together. Had enough time between the two to build a new rig. I will post the specs below. I wanted to OC (first time) but the temps seemed to be running a little warm at start up, and I never had time to get around to messing with it. So, here are my specs (everything is currently stock clock):

Case:
Antec Three Hundred
http://www.newegg.com/Product/Product.aspx?Item=N82E16811129042

CPU:
Intel Core 2 Duo E8400 3.0GHz
http://www.newegg.com/Product/Product.aspx?Item=N82E16819115037

MoBo:
Gigabyte GA-EP45-UD3P
http://www.newegg.com/Product/Product.aspx?Item=N82E16813128358

GPU:
HIS ATI Radeon 4890 1GHz
http://www.newegg.com/Product/Product.aspx?Item=N82E16814161276

RAM:
G.Skill 4GB (2x2GB) DDR2 1066
http://www.newegg.com/Product/Product.aspx?Item=N82E16820231166

Cooler:
Xigmatek Dark Knight
http://www.newegg.com/Product/Product.aspx?Item=N82E16835233029

Power:
OCZ StealthXStream 700W
http://www.newegg.com/Product/Product.aspx?Item=N82E16817341019

Here are the readings at idle:

E8400:
Core 0- 41C (105F)- 1.15V
Core 1- 35C (95F)- 1.15V

Radeon 4890:
Core: 57C (133F)- 1.05V

I was wondering if any or all of the following would work.
1- add the extra 3 fans that do not come in the case
2- take off and reinstall thermal paste (first build, may have not used it properly?)
3- change cooler

Or, are there any other suggestions? Are these temps even something to be worried about. I'm not going to try to my processor up to 4.0 (more like 3.4-3.6) but I was also thinking about bumping up my RAM and GPU clocks also. Thanks for the help!

Idle temps don't really tell us much, what are the temps like after 5-10 minutes of prime95 large FFTs?

Essentially, <60*c is downright cold, <70*c is excellent, <80*c is ok, and >80*c is generally considered too hot.