My new 6400+ black edition is running at 58-60 degrees when idle, 65-70 when doing anything and most of the time just shuts down as its too hot, im guessing this is not normal, my cooler is just a regular one, but its not overclocked or anything, i put about a rice size amount of thermal on the cpu and spread it, used Akasa silver if i remember rightly.
Check the airflow in your case by removing the side panel, if temps drop you need to 'optimize' airflow in your case and clean up cables. Also check that your heatsink is correctly seated, id recommend you reseat it again just to make sure it right and remember to apply new thermal paste
purchase Artic Silver 5 thermal paste and go to there website for detail instructions on how to apply it to your specific processor.
There are different methods of applying paste depending on brand, cores sockets etc.