I know this is an old thread but the solution I have found works for me most of the time when I'm having this problem. I've tried to delete history that doesn't work, I've also tried to cleanup mesh but there is nothing wrong with it.
So the solution is to simply select the mesh export it as obj then re-import it. Then it can be smoothed without a problem. For some reason this fixes the problem for me. Hope this helps some of you with this problem.