I'm looking at the very same error poping erraticaly over the weekend and also today. All the IE settings are done as suggested
although I don't understand the need to "Allow software to run or install even if signature is invalid"
Cant SE sign their own software ??

Given the erraticity of this behaviour, this is not problem of missing / invalid certificates. The time CAN be a problem if SE loging servers are so slow that time-outs occur thou.