I've got two computers running NIS: a laptop with 2011 and desktop with 2010. Both have been fine for the most part, but my desktop just started failing update checks. It sits for about 2 minutes until giving the failed message in the info pane. Odd thing is, it received one of Norton's quick updates the first time this occured about 20 minutes ago even though update status was "failed to check for updates."
The same thing occurs after rebooting. I went ahead and tried my laptop, and it interestingly took it a bit longer to exit processing updates status. It still got them though. Is this an update server problem on the rise, or just me?