Error Starting NAS on NAV 2015

When I tried to start the NAS on Dynamics NAV 2015 for the first time, I ran into this problem in the event log:

Server instance: DynamicsNAV80
The Microsoft Dynamics NAV Application Server session for tenant 'default' has permanently failed and will not be restarted. Reason: Type: Microsoft.Dynamics.Nav.Types.NavDatabasePasswordException
SuppressMessage: False
SuppressExceptionCreatedEvent: False
FatalityScope: None
Message: The user ID and password are not valid. Please try again.
at Microsoft.Dynamics.Nav.Runtime.NavSession.Open(Boolean useUserPersonalization, Byte[] licenseToUse)
at Microsoft.Dynamics.Nav.Runtime.NavApplicationServer.<RunOnceAsync>d__b.MoveNext()
--- End of stack trace from previous location where exception was thrown ---
at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)
at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)
at Microsoft.Dynamics.Nav.Runtime.NavApplicationServer.<StartAsync>d__7.MoveNext()
Source: Microsoft.Dynamics.Nav.Ncl
HResult: -2146233088

It turned out that I had to change the user on my NAV service to something else the default Network Service account.