I would say that the desktop should be the *last* thing you replace.
First come the servers - migrate from windows or unix to linux, keeping the front-end as similar to the original as possible. Main problem here is if you are a exchange and outlook site, most exchange replacements are simply not up to scratch, or cost as much as just going with exchange - you want an outlook front end, with support for folder sharing and calendar busy searches, and in most cases that just isn't going to happen.
Next come the apps - and in most cases, this is easier. As you upgrade and replace, select those which have cross platform clients that look pretty much the same on both linux and windows; if they are in fact entirely platform independent (java?) so much the better, and if you can arrange for them to be web deliverable than better still.
Finally you can swap out the desktop - on the given day, the start button becomes a penguin button - but gives pretty much the same menu, with the same apps, looking and acting the same.
However, all this may change - the new target is no longer the server or desktop, but cloud computing - at which point, it no longer matters what you have front end or back, provided the front can render and the back run whatever cloud format comes out on top.