I usually discuss any change I either foresee as necessary or that I think might enhance the picture with my client before making any changes. Like DJ said, some changes are out of necessity because there just isn't enough information to "restore."
However, I recently had a client who had a photo taken with Tiger Woods at night with a flash. The composition was terrible in that Tiger's large SUV filled the photo with the people fairly small in comparison - and the camera focused on the SUV instead of the people, so the people were out of focus. I was asked to get rid of the red-eye, the reflection from the reflective tape on Tiger's jacket and crop it so that the people were more prominent. As it turned out, when I cropped it, the SUV seemed more of a distraction in the background than anything else (even after blurring.) I gave my client the option of putting in a different background, but he declined saying that the SUV was part of the whole "experience".
So, I think it's always good to talk something over with a client. You never know if what you consider non-essential (to be cropped/blurred/painted/removed) is actually an important part of the photo from the client's perspective. I think this just goes along with being good at asking the right questions to understand what your client's goals are for the photo because regardless of what you think looks best, if the client has a very clear picture in his/her mind as to what the final result should be, you need to know that and also know if it's possible to achieve that (within a price that they're comfortable with.)
Jeanie