I've seen a few of the service startup issues resolved by increasing the service timeout parameters:
1. In Registry Editor, locate, and then right-click the following registry subkey:
HKEY_LOCAL_MACHINESYSTEMCurrentControlSetControl
2. Point to New, and then click DWORD Value. In the right pane of Registry Editor, notice that New Value #1 (the name of a new registry entry) is selected for editing.
3. Type ServicesPipeTimeout to replace New Value #1, and then press ENTER.
4. Right-click the ServicesPipeTimeout registry entry that you created in step c, and then click Modify. The Edit DWORD Value dialog box appears.
5. In the Value data text box, enter the desired timeout value in milliseconds and click OK. For example, if the new service timeout should be 60 seconds (60000 milliseconds), then enter 60000. (I suggest setting this to 120000).
6. Restart the computer. You must restart the computer for Service Control Manager to apply this change.
The short of it: It looks like we changed the signing process for the new rollup and we are having to perform validation against the binaries. Those machine accounts that don't have Internet access (say no access behind a DMZ, or proxy requires authorization) will experience this issue.