The instructions and tools here mentioned are suitable to remove infections from the 'W32.Klez' family. Not only for W32.kleze.e aka Klez.e but also for f.i. W32.Kleze.H aka Klez H.

Removal Tools:

BitDefender:
http://www.bitdefender.com/bd/site/downloads.php?tool=AntiKlez.exe&what=2

F-Secure:
ftp://ftp.europe.f-secure.com/anti-virus/tools/kleztool.zip

Kaspersky Labs:
ftp://ftp1.avp.ch/utils/clrav.com

Symantec:
http://securityresponse.symantec.com/avcenter/venc/data/w32.klez.removal.tool.html

Trend Micro:
http://www.antivirus.com/vinfo/security/readme_worm_klez_4.04.txt
http://www.antivirus.com/vinfo/security/fix_worm_klez_4.04.zip

Manual Removal.
You MUST follow all the steps in order to be sure this worm does not re-infect your system:
Keep in mind that %System% can be either Windows\System or Windows\System32:

Step 1:
Click Start > Run and type Regedit.
Follow the paths using regedit and delete the following values (if present):
HKEY_Local_Machine\Software\Microsoft\Windows\CurrentVersion\Run\Wink[any characters]\ %System%\Wink[any characters].exe

HKEY_Local_Machine\Software\Microsoft\Windows\CurrentVersion\Run\WQK\%System%\Wqk.exe

Step 2.
Follow the paths using regedit and delete the following values (if present):
HKEY_Local_Machine\System\CurrentControlSet\Services\Wink[any characters]

ATTENTION Windows 2000 and XP Users.
The worms adds 'wqk.dll' to the following Registry key:
HKEY_Local_Machine\Software\Microsoft\WindowsNT\CurrentVersion\Windows\AppInit_DLL

Delete 'wqk.dll' from above mentioned Registry key if exists.

Step 3.
Exit the Registry

Step 4.
Make sure Windows is configured to show all files and show file extentions.

Step 5.
Start > Find > Files or Folders.

Step 6.
Search for wink*.exe on your Windows system and delete all files found.

Note: You may not find the virus file if Windows is not configured to show all files on your system (even hidden ones).

Step 7.
Search for wqk.* on your Windows system and delete all files found.

If you are running Windows 98, Windows ME, or Windows XP: since this worm can infect other files that might run during startup, perform the following steps to prevent those programs from starting automatically every time Windows starts.

Step 8.
Click Start > Run > Msconfig.

Step 9.
In the window that appears, click on Selective startup.

Step 10.
UNCHECK Load startup group items or Load Startup Items.

Step 11.
11. OK your way out.

Step 12.
Reboot your system.

After scanning your system with an updated antivirus scanner perform the next steps.

Step 13.
Click Start > Run > Msconfig.

Step 14.
In the window that appears, click on Selective startup.

Step 15.
CHECK Load startup group items or Load Startup Items.

Step 16.
OK your way out.

Step 17.
Reboot your system.