For what it's worth - my scenario seems to have been the same, with the same (or at least similar) symptoms & error(s):  

Install Notes 9.0.1, then install FP2, which failed, and failed during the rollback operation. Running Notes subsequently failed. Running the FP2 installer again did revert the client to 9.0.1, then Notes ran properly as 9.0.1. There was a previous version of Notes installed on this machine, but I'm not sure exactly which version. Notes 9.0.1 was not installed over the top, but the previous version was removed, and Notes 9.0.1 was installed using the 'new' directory structure - so it was a 'clean' install to a 'clean' directory.

Using the NICE tool to 'completely' remove Notes and the registry entries did not work for us, either. Clearing the directory structure after running NICE didn't help, either.

Since we only had one user that was affected, we ended up giving the user a new machine. I'm still trying to get my hands on the old machine (it's in a remote location) so that I can do some further tests.

I say that we only had one affected user, but I've received anecdotal evidence that we've had more that one issue, it's just that the tech(s) involved at the time(s) left the machine with 9.0.1 with no fixpacks and didn't pursue the issue. So we may see it pop up again.

If I can get my hands on the affected machine - where would you like logs sent?

Thanks!

--------------------

Update - I have the test machine - I can reproduce the FP2 install error that I am receiving - where would you like me to post the logs? (Approx 4Meg)