vordmeister - 7:31 pm on Apr 21, 2011 (gmt 0)
I'll be spending the weekend doing something very similar.
For me the new domain was set up and pointed to the server 2 weeks ago to make sure it resolves for everyone by the time of the move (dns takes a time to propagate). The new domain will be disallowed by robots.txt until the site is set up and working on there. Once it's set up and working I'll allow on robots.txt and put the 301 redirects in on the old site. Then I'll change links and any google stuff (they can go through the redirect initially).
My design change happened about 2 weeks ago. Main thing with timing is to try to see what effect the design change has as opposed to the domain change. You never really know which has what effect and effects can be delayed, though it's worth doing the two on different dates - if traffic stops dead just after a change then it gives you less to debug.