This occurs because the NETWORK SERVICE account is not granted the appropriate user rights.
Look into this article on MS, if the server is not a DC, use Method 1 or Method 2. If the server is a domain controller, use Method 3 or Method 4.
Don't get confused that article is about Terminal Services, instructions there apply to any service (any service that is configured to start by using the NETWORK SERVICE account may experience similar symptoms).