After a WSUS Rebuild, I started noticing that Machines, although associating with WSUS were showing up that they had not yet reported to the server, upon investigating this it was discovered that the clients were erroring and displaying error code 800B0001. The machine in question hosting WSUS is a 64 Bit Server 2008 R2 machine, with these details in hand I go off looking for a solution.
Looking for solutions to this I came across several sources indicating that this is a known problem, and thankfully that there is a solution available from Microsoft (http://www.microsoft.com/en-us/download/details.aspx?id=29999)
I simply installed the update, and restarted at then end as asked by the installer, once the server is back up I went back to the same clients and re-ran windows update, and off it went working again.
Nice Simple fix, if only everything was that easy