I am having the exact same problem installing 3.5.5 on Windows 7 x64. I have read the FAQ repeatedly, (incidentally it is very arrogant to suggest that the information in that post "it always, always solves their problem." )
I successfully installed 3.5.2 which was working up to a point - this could be due to a Windows or .Net patch? Basically, Paint.Net would not load, it would lock up and one of my CPU cores would may out. Trying to uninstall it would produce the same behaviour, but with either SetupNG.exe or SetupFrontEnd.exe. So i used the Windows Uninstall clean up utility to blitz it (as per your recommendation).
Then tried to install 3.5.5 and after granting admin rights, and the installer briefly popping up and successfully extracting files, i hear my machine make a default ping noise and in task manager i can see that SetupFrontEnd.exe is maxing out cpu core once again.
This from the SetupShim log, no others exist.
--- 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 = false
bIsNetfx35SP1Installed = true
bIsNetfx35SP1ClientInstalled = false
bIsNetfx20Installed = true
bIsSupportedNetfxInstalled = true
bIsNetfxInstallerPresent = true
PreInstallPrompt() returned true
InstallNetfx() returned 0
Launching Paint.NET installer. bRebootRequired=false