A few points.
I suggest you roll out "side by side"whereever possible. Have the new phone and their existing phone on the desk at the same time. You can then have the users test the phones, and make outgoing calls, etc.
The telco can transfer DIDs from your old to new very quickly, and love doing it on the weekend because they get overtime.
Remember to tell your users to get all the old voicemail off their old boxes.