I recently had a discussion with some guys from Citrix and asked about the optimal way of upgrading Presentation server 4 to Xenapp 5.
Here is there recommendation
1) Upgrade the licensing and upload the new license file onto the license server
2) Run the upgrade on the server acting as the Resource Manager
3) Upgrade the remaining servers in whatever order you choose