Hi,
Just looked at the configuration for this machine and it has no gateway defined on any of it's network cards. This is possibly by design, since our systems often run on private networks without external gateways. However, in this case, the working machines do have a gateway defined on the one of their cards, so I have added this gateway to the one with a problem. It looks like the schedule Liveupdate has just run for the first time, but I will post back and confirm in an hour or 2. In the meantime, I am collecting the requested logs, just in case there is still an issue.
Looking good so far though guys, thanks very much for you help! :)
James