Real World
An "all at once" deployment is the option that best serves IT, but, realistically, the staged method is more in alignment with what the IT department is all about - service.
Factoring in the loss of productivity due to the software change alone, rolling out more than a few users or a single department at a time simply isn't smart unless your company is quite small. And you should also consider user training - moving to XP might be a no-brainer for us, but blue-haired secretaries are much less adept and far more intimidated about such a move. Even your more savvy users will need a little coaching and some adjustment time.
I do advocate migrating work groups or departments in single shots, however, so that those who routinely work closely together can be learning the same new stuff at the same time.
And you've got to "phrase" the migration in terms that make it appealing to the users, despite the fact that your primary motivation may well be to make life easier for IT.
