I recently got a new system with windows 2000 pre-installed. PAF 4.04 installed and appears to run without any problem. This may give you reason to hope, but unfortunately does not point the way to a solution to your problem. Make sure the user account you are logged into when installing has Administrator rights. Also try installing immediately after booting and logging in.
However, I have not been successful in installing PAF Companion 2.0. The Setup program refuses to do its thing ('OS not supported' or words to that effect). I suspect it will run fine, once installed, since it ran on NT4, and may try copying the files over from another machine after installing it there.