I'm seeing this issue too, since I had to reinstall WSUS and the SCCM 2012 SUP for another issue. I only use SCUP for Adobe Reader updates. I have Windows 7 32-bit and Windows 8.1 64-bit clients with the exact same issues. Can't see what's going wrong. The certs are getting to the machines, Trusted Publishers and TRusted Root..
Correct GRoup Policy is visible in gpedit.msc etc
Would be to hear if any possible solutions out there.