the temps you posted, are those idle temps? if so they are way too high, I would suggest the the cooler is not correctly seated.
Go back into your case and check the push pins that hold the cooler to the board, they are a useless design and come unclipped quite easily, I bet you'll find one or more not correctly clipped in.
CPU fan speed, you do have it plugged into the correct header on the m/board yes??
Can you post a pic of the inside of your case?