I know that the days of the "big redesign" are largely over, giving way to smaller, more iterative approaches to improving a site's experience. However, there are still instances when a total makeover is requested or required by the client. When these big redesigns happen, my experience is that it's either that the underlying (current) architecture is so flawed as to not be helped by small changes (or, the amount of time it'd take to get from A to B is too great at this pace), or there's a significant change of some sort that necessitates a large-scale redesign (adding huge chunks of new functionality, etc.)
Naturally, our job as user experience designers is to craft a new architecture that makes sense to the users, is easy to navigate, etc. However, there's an inevitable uncomfortableness on the part of the some of the users when such a redesign is launched, that lasts until they are oriented enough to understand the translation between the old design and the new (particularly for repeat users).
How do you manage this transition, and how do you explain to clients that the initial feedback, while showing signs of discomfort and temporary confusion, are not a result of the design work itself, but that of the transition?