Absolutely! Before I'll take any client, they have to understand that we will indeed be making changes to their site (visible ones). And we provide them with the sorts of changes that might be necessary. Like we tell them they may have to implement a whole new navigation scheme. And/or change the anchor text of some links. And more likely than not, change the wording on the page.
So they know what's coming down the pike. Now, if for some reason they can't do everything, or can't do some of it, we can usually compromise. Sometimes you can do just 10% of what you want to do and it can have a huge effect.
You do need to listen carefully to them as to why they claim they can't make the changes. You want to be sure that you're not actually making their site worse for their site visitors. Remember, they have a specific marketing message and other things that you have to be cognizant of not messing up.
Back in the old days when I first began, I didn't really get that part and would recommend changes that might screw with some of their other marketing or branding initiatives. Now I'm much more aware of those things and understand that they ALWAYS come first.