I had the same problem on 2 separate servers with new installs of 2010 R2. The following rectified the problem:
From Control Panel, change LiveUpdate Configuration HTTP settings to "I want to customise my HTTP settings for LiveUpdate". Enter proxy IP...