I've been having the same problem, have tried disabling my anti-virus and the other suggestions in the FAQ but still not able to complete an install of 3.5.5 on Win7 x64. Contents of PdnSetupShim.log below:
--- Paint.NET SetupShim starting, lpCmdLine='/suppressReboot', nCmdShow=10
CoInitialize(NULL) returned 0
pIAA = CoCreateInstance(CLSID_AutomaticUpdates) returned 0
pIAA->Pause() returned 0
Checking OS requirement
bIsWin7 = true
bIsVistaSP1 = true
bIsVista = true
bIs2003SP2 = true
bIs2003 = true
bIsXPSP3 = true
bIsXP = true
bResult = true
EnsureOSRequirement() returned 0
Called EnsureTrustedInstallerIsEnabledAsync()
Checking .NET requirement
bIsNetfx40ClientInstalled = true
bIsNetfx35SP1Installed = true
bIsNetfx35SP1ClientInstalled = false
bIsNetfx20Installed = true
bIsSupportedNetfxInstalled = true
bIsNetfxInstallerPresent = true
PreInstallPrompt() returned true
InstallNetfx() returned 0
Launching Paint.NET installer. bRebootRequired=false
Done. nReturnVal=-1073741701
Sleep(1000)
--- Exiting, nReturnVal=c000007b