Every time Facebook makes user interface changes, people hate it. When Google makes a change, there is almost no reaction. And there's a reason for that.
Facebook is really lucky to be in a position where no matter the controversy (exposing personal data, stolen ideas, site redesigns), they keep growing. They've recently hit 500 million users. The struggling individual user's anger over relearning the site layout is overridden by his or her desire to stay connected with the community. In a lot of markets, users would just switch to another product. So I have come to expect an uproar when changes appear on such a well-used application. Not so with Google's Gmail.
The Gmail Update
Gmail gets an update, and while admittedly it would take a lot to turn away their 40+ million users, nobody seems to care. It is possible that the changes are being overshadowed by other announcements, including Google Wave and the open Internet policy. But the real reason no one has much of a problem is because the change to the site is so small. Keeping it so limited has the added bonus of highlighting the new features for the user. By keeping so much the same, the change gets magnified. Imagine if you woke up tomorrow and found a shiny new box in your room, but everything else was the same. You might be skeptical, you might be angry, you might be excited, but you would still go examine it. You could figure out how to deal with that box being in your room.
Apply the same analogy to the way Facebook makes changes. You wake up tomorrow, and not only is your room rearranged, but the door has moved and the windows that used to face west are now on the east. This might be exactly the way you would have set things up in the beginning if everything could be made to your own specifications. But it would be hard to handle because you did not get to make the decision. Somebody else came in when you were sleeping and changed a lot of the rules. And even worse, you might not even realize that now there is a new feature available, because you are too busy trying to find your pants and get out the door.
Not many of us have 500 million users to appease. However, it is important to be sensitive to your target audience with each change to your site. Does it significantly disrupt their regular interaction without a noticeable improvement in functionality or performance? If so, have the patience to update gradually. Give users shiny new features, one at a time. Don't uproot them into a completely new home overnight.