If you incrementally add one new feature then any existing user may or may not use the new feature. But what happens if you radically overhaul a site, changing its style, changing the items, style and placement of the navigation and improving but changing core functionality?

If you do that you're probably making a mistake anyway. You should be constantly releasing changes, and if you are, it would be hard to accumulate enough unreleased stuff for it to seem like a radical overhaul.

If you have a relatively large userbase, I would be hesitant about changing too much too fast. I would set up a poll or discussion thread in your site's news blog to get a feel for how your suggested changes would be received. If they like it, go for it. If they don't, find out why not.

However, changing one thing at a time is a good suggestion. Adding features helps improve the usefulness of your site and allows you to appeal to a broader audience. And if the users hate your new addition, they will sure as hell let you know.

Can you not throw away what's bad and keep what's good during your overhaul?...

It's generally really hard to throw away stuff, even if it's bad. Users get used to things in the UI even if it's bad.