Agreed, it's definitely not normal those are max load temps not idle temps. Some product reviews can attest to this:
http://www.overclockersclub.com/reviews/cm_hyper212_evo/4.htm
http://www.guru3d.com/articles_pages/cpu_cooler_roundup_2013_q1_review,8.html
Some things that you can check, apologies in advance if I'm hashing over prior knowledge:
1. Confirm that your idle state really is idle and there are no background processes running
2. Try re-applying even more thermal paste than you did before but also ensuring you don't apply too much that it starts to ooze out of the sides when installed. Also avoid creating air pockets when installing the cooler as it'll create inefficiencies in the cooling process
3. Check that the CPU fan power header is firmly installed
4. Check if the CPU fan speed is running at a reasonable RPM for your idle state
If you're confident of all of the above then the problem most likely lies with the cooler unit.