71 is within what I would consider to be an acceptable range, though it's certainly at the upper end of acceptable. It's up to you at this point whether you want to add a new cooler - the processor should do fine with the current cooler, but with a good aftermarket one, you could probably get load temps down to 55C or so.
I agree, those are warm. I run the q9400 with an aftermarket cooler, a simple 4 heat pipe aluminium fin head sink with a 90mm fan, and at MAX load with prime95 I get 53-55degrees (your idle temp). when it idles it goes back down to about 27-32degrees, my room temp is around 20-22 degrees. and this is with an overclock of 3.2GHz
Its always good to upgrade your cooling from stock. you don't need to go outrageous with liquid cooling or anything but anything is better then stock.