When you changed the motherboard, ideally you should have removed all traces of the old thermal compound & replaced it with fresh stuff. Motherboards never do come with thermal compound, you only normally get this supplied with heatsinks.
I suggest you buy some good quality thermal paste, such as Arctic silver 5 or similar. Whichever one you get, make sure it is suitable for your cpu & is silver, rather than silicone based.
You can also buy a solution for removing old thermal compound.
The link below is to Arctic's instructions page. This will give the the proper procedure for removing & applying fresh paste :http://www.arcticsil...nstructions.htm
Apart from the cpu compound, I suggest you also look at providing better airflow in the case. You said you have another fan you can put. Where you place the fan depends on what fan mounting areas are available in the case. Essentially though, you want to have the air blowing in one end (normally the front) & blowing out at the other end. Do not have the fans all blowing inwards or all blowing outwards.
Also check for obstructions to the air flow, typically ribbon cabling etc that may be hanging down & obstructing the flow of air.
Finally, make sure you clean out any dust that has built up in the case, especially around the case fans, cpu heatsink/fan, power supply fan etc. Use a can of compressed air to clean the dust out.
Re. cpu temps. The lower the better obviously, but you should aim to keep the cpu temp below a max of 50C under load, and around 35 to 40C max at idle.