I don't think you are necessarily doing anything wrong. Sounds like another service it depends on hasn't fully started yet. It is possible that any dependencies are not configured at all. It also appears that the service requires full admin to run.
As a workaround, I would configure the service properties this way:
On the Log On tab, use the local
On the Recovery tab, change the first
and second failure events to restart
It's not the most elegant solution, but if it's purely an issue due to permissions and timing, this should resolve it.
It's also worth looking in gpedit.msc and checking out the Computer Config | Windows Settings | Security Settings | Local Policies | User Rights Assignment | Deny log on as a service and Log on as a service entries.