I was having the same problem or similiar, Paint.NET would install on my Win7 Beta Build 7000.
After trying different stuff I installed one version down, so not 3.36 but 3.35 and it working fine!
Must be some code in the new version giving Win7 a hard time.
Try installing an older version and let us know what you get. Messing with the registry is never realy a good idea.
Greetings
Corleone