Just to let everyone know, removing the Visual C++ Redistributable did not resolve my clients problem.
However, SUPERAntiSpyware seems to have sorted it out. It found 54 infections including Generic.Trojan Unknown and was the only Anti Malware/Spyware/Virus software we could a) Download, b) Install and c) actually run succesfully!
All appears to be ok now but just want to find out where the infection came from as it's a reasonably new re-install...?