A 301 between two EXISTING sites is not the same thing as georgeek's opening question about moving to "a brand new domain."
Yes, I have helped sites move to a brand new domain. Minimum of 6 months lost traffic, often more depending on the strength of the legacy site.
My best advice -- first, put up a small selection of urls on the new domain and establish a single Webmaster Tools account that authenticates you as the responsible party for BOTH domains.
Next, build a game plan for your 301 redirects. Do not 301 the entire old domain to the home page of the new domain. But also, do not use a separate 301 for thousands of urls to thousands of other urls. Use a 301 for the most critical relocated urls (nice Google traffic and/or nice backlinks). The rest of "lower importance" the URLs can serve a custom "we have moved" message with a true 404 http status code.
Some people prefer using 301 for all pages. My experience is that Google takes a long time to sort all those 301s, and my more "surgical" approach has worked out a bit better. However, it is still not a fast process in any case.
One other step - work with your backlinks. Contact major backlink owners and request a change - many will be glad to oblige because it makes their site look better. Make it easy for them in your message. Tell them what url on their site has the backlink, and give them the new address.
Take it one step further. You want to establish NEW backlinks as soon as possible, so let a lot of people know about your new site, in a way that encourages new links.
These steps can also help for moving between two established domains - and that situation can often be resolved a good bit faster with Google. Moving to a new domain has usually been a dreadful experience.
One last comment - be sure that the new domain really is "new" and not a domain with a dark past.