Perhaps the removal tool works better in safe mode (similar to avast! removal tool).
Not neccessary to run the NOD tool in safe mode SKY, well the info states just to run it with no mention of safe mode.
T_L_O_T_D it might help to reset your windows firewall to default to start with and also set avast back to default ( settings/troubleshooting ), also check device manager-click on view and show hidden devices to see if there maybe some NOD32 drivers still installed.
"Note" that it should not be neccessary to add exclusions for avast to the windows firewall unless you have activated the outbound protection.
Unless your system is actually connecting through a proxy then changing it so will do nothing, stick to the auto detect ( default ) and if there are then issues try direct connection.
If none of this has still helped then i'd suggest a clean install as remnants of NOD could have corrupted avast.