steveb: What has changed is (amazingly) some words not in a query are now valued just as much as words that are in the query (!). And the importance of page title itself is less important overall. (It still is very important, but where it might be worth 114 points a few months ago it is worth 93 points now.)
So it's a bad idea to change your titles randomly, because tweaking a title can't help you with either of the above things. That is especially true in regards to the second factor.
In essence, Google's choices have been to move away from relevance... and the more precise a searcher searches, the further away from relevance Google gets. A webmaster can respond to this by making their pages more stupid (on a page about someone named Marie sometimes use "Mary" and "Mariah" instead), or just make pages that are not stupid and assume you'll still rank decently in 2010's Google-the-in-exact while also ranking just fine in the future when Google finally gets over its stubbornness and realize this change is a really and truly stupid one.