Dont worry at all, anything below 70C is considerd "safe", my newcastle idles at 34C and goes up to 49C under load.
If your really worried about temps then its better to try and improve the air circulation in your case. To do this you need intake fans at the front of your case (preferably at the bottom) and exhuast fans at the back of your case (preferably at the back). Small things help as well like ehaust blowers or extra forms of air circulation like the Antec Vcool (draws in air via a pci slot).
And the thermal paste your using takes about 150-200 hours to settle, over that period you will see a 1-10C change in temp.
Alex