My colleague Nik Stevenson-Molner got the same (or very similar) problem and solved it by uninstalling Internet Explorer 11 upgrade, leaving the Internet E 10. I tried that to no avail so far...
ESRI Support had me uninstall Internet Explorer 11 completely.
It is not necessary to uninstall explorer 11 and 10. In Windows7 there is an option to shut off windows functions. When you do that, the tool works correct.
Support should know that, though...
Turn off Internet explorer in Windows7
Open the Control Panel
Choose Programs
Choose Programs and features, turn Windows features on and off
A panel shows - turn off Internet explorer
And go ahead with simplifying!
I have the same problem since 10.1
Shutting of IE changes nothing...
Used python scripting as workaround
This issue is still around in ArcGIS 10.2.1. I tried to run Simplify Polygon this morning and could not find a place to enter the Tolerance
Luckily, the workaround advice offered by Emilly Foster on batch processing the tool works (see above in thread).
Chris Donohue, GISP