@Tedster, I'm going to be doing this with a domain that got smashed in Penguin - not b/c of Penguin but because I've been wanting a better domain name for ages, and right now, with only 20% of my normal traffic, this seems like a good time to make the move.
I'm curious to hear more about the 10-15% loss of link juice that you mentioned above? I think my backlink profile is so weak that it isn't worth worrying about, but I just wondered how this would affect the site. Lower it in the rankings a bit further? It can't get much worse right now, so that's not really a problem.
I have very few quality backlinks, but I'm pretty sure those sites will be willing to update their links to me, so that should help.
Also, what about other search engines? Do they typically handle this as gracefully as Google, providing I get everything right?
(I did this once on a hobby site where I changed the TLD, but this will be the first time I've truly rebranded a site.)