If you have any firewall installed on your local system then it will happen.So disable the firewall and check.

There is also another possibility like if there is any SPyware or Adware it will give error like that

1. Download the following file to the Desktop:

http://www.spywareinfo.com/~merijn/files/cwshredder.zip 

2. Locate the downloaded file, double click to open it, double click to run the
file CWShredder.exe in it and follow the instruction to remove all the found
spyware programs such as "CoolWebSearch".

Thanx for the response inbarasan, forgot to mention that our antivirus has full anti adware, spyware built in.  The firewall is definitely disabled when Windows Update is ran and the problem still occurs.

chalapa, we will attempt an uninstall/re-install of IE at 17:30 GMT.  I'll update this as soon as its done.  Thanx

Usually when I have problems with windowsupdate.microsoft.com I have to perform the following procedures (for Directx/general stop error problems)

1)  Stop the Windows Update service: Start -> cmd -> (from c:\ prompt) c:\ net stop wuauserv <enter>
2)  Delete the SoftwareDistribution folder from c:\windows (XP) or c:\winnt (2k)
3)  Start the Windows Update service back up:  c:\ net start wuauserv <enter>

Try the windows update site again.

Hope that helps!

-Brock

Heh, just to clarify, the folder to remove is "%systemroot%\Software Distribution"

The folder will be rebuilt by Windows Update when you hit it after restarting the service.

This issue may occur if you cannot download the ActiveX component of the Windows Update Web site.
Method 1:
 Add the Windows Update Web sites to the list of trusted sites in Microsoft Internet Explorer <<which you have done

To add the Windows Update Web sites to the list of trusted sites in Internet Explorer, follow these steps:
 1. Open Internet Explorer.
2. Click Tools, and then click Internet Options.
3. On the Security tab, click Trusted Sites.
4. Click Sites.
5. Click to clear the Require server verification (https:) for all sites in this zone check box. <<<<<<<<---------this one especially

6. In the Add this Web site to the zone area, type the following Web sites, and then click Add:
http://Windowsupdate.microsoft.com
http://v4.Windowsupdate.microsoft.com
https://v4.Windowsupdate.microsoft.com
http://Download.Windowsupdate.com 
7. Click OK two times.

If running zone alarm put the MS site into allow.

Have you rebooted the server?

Thanks for all your responses unfortunately we still have the same error.  Merete, I have double checked the list of trusted sites (https checkbox is unchecked) and the servers have been rebooted.  Also, our firewall is definitely configured to allow Windows Update through.

Brockbuss, nice try but when we open up the browser again the same error is returned (we did observe the "Software Distribution" folder being re-created).

Chalapa, I'm just uninstalling/re-installing IE as we speak.  Didn't have time on Friday as I've got to uninstall Windows SP4 1st (kb277624) so that IE6 reappears in the Add/Remove programs list.

uninstall Windows SP4 1st << may actuially help you, this is after all a kind of repair when you re-install it.

And another must be the biggest I have sen yet came across it by chance and was just blown away with staggering amount of problems and solutions shown here
Last Updated: September 5, 2006
Problems Accessing Windows Update
http://www.helpwithwindows.com/techfiles/winup-errors.html

Yeah, sometimes it works...   sometimes it doesn't.

You may want to check that the automatic updates service is set to automatice and is running.  We have to change ours from manual to automatic to allow the manual updating.  Go figure!