Hi,
Just received a friend's mail describing the same problem, dll re-registerded did nothing too.
As it happened to my friend's computer just after having installed Avast, it told him to uninstall it and the problem was solved.
He reinstalled Avast after an sidebar is still OK.
So, maybe you could try deinstalling your AV to check if it solves the problem, deactivating it may work but i guess that some entries have to be cleared.
Check also that if you changed AV that the old one has been deinstalled entirely, for example on a PC which had Kaspersky for ages and then moved to Nod 32, in the Windows firewall control panel settings, Kaspersky were still appearing as the main firewall (just the name was present because of some weird registry entries).
Hope it helps.