I just upgraded from 3570 to 8500, and my temps would be at max 70 degrees under load (gaming) with CPU-heavy games on the 3570. The 8500 is even better, going up to a max 55 degrees under load (CPU-heavy gaming). These temps are on the stock Intel cooler (as of writing this post any way).
You probably just need to clean out the dust in your casing, re-apply the thermal paste and re-seat the cooler.