We spent the better part of 2008 preparing to upgrade (from 8.0 M030 to 9.0 M050), and successfully did so between Christmas and NY.
Users will experience relative drastic page layout changes, but they seemed to get used to it in just a few days. There is not much in the way of major functionality changes, but there are a large number of small very good and very helpful changes / additions. For non-Pro/E users, we left users on their own for the first 2 weeks, then had Q&A training sessions to fill in gaps in understanding. For Pro/E users, we held about 4 hours of training ahead of time.
That said, there are some very important admin changes to really pay attention to, plan for and test. They include (not a complete list):
A) Major changes to ACL's. See attached analysis (tied to our lifecycle states, not OTB states).