Unfortunately, the problem is fairly complex and will depend upon the rest of your environment. Is each PC entirely different? or do you have 20 or this model, 15 of that model, 30 of x model etc? If you do have some significant commonalities you may want to look at the disk image option. However, this will not preserve any of the previous settings.
I'm assuming there is a network involved? If so, what is the server OS? If it is NT and you are using SMS you could use this to perform your upgrades. If it is NetWare 4.11 or greater take a look at ZenWorks. These would require some configuration to setup but would aid in this process significantly.
There are a couple of other products which are desinged to aid in OS upgrades. I don't remember the exact names and I think they were more suited toward migrating to NT workstation from 95/98. These would probably cost you a bit though.
If you don't have any of these tools currently or don't see much future use for them you may want to consider the low te