I been working on various really large redesigns. They all seem to share a constant thread regarding poor communication on why things have changed in the past. How do you handle informing your users and keep them inside the loop? Are there ways you handle showing subtle changes? Do you find that they not really care how the sausage is made? I'm talking around a non-product SaaS type of site.

Do I need random tool tips around the site noting changes like "You said our nav sucked, so we fixed it, learn why we did this"?