Creating subscription gives error: "The specific error is: 0x80070569: Logon failure: the user has not been granted the requested logon type at this computer." (4333804)

Subscriptions are not being sent out and the associated Scheduled Task states "Could Not Start".

Also, the following error is logged in the Scheduled Tasks log file:

"The attempt to log on to the account associated with the task failed, therefore, the task did not run.
The specific error is: 0x80070569: Logon failure: the user has not been granted the requested logon type at this computer. Verify that the task's Run-as name and password are valid and try again."

The same error above will happen when creating subscriptions with the wizard.