Warning: [Video] Recording Failed
The culprit is probably an app that accidentally doesn't release a critical lock.

In my case, it was the Cortana app that was causing the issue. It has a setting for the "Hey Cortana" hotword in the app, which requires that the application grab the microphone lock. It seems like the app, when quit, never released the lock, and so the camera couldn't have access to the microphone (and couldn't record)

If you don't have Cortana, try scouring your app list for apps that will obtain a lock for (and have the possibility of keeping it across runs):


Microphone
Camera
Storage


P.S. I've also heard that this issue can be caused by interference from Smart Stay, but I've never had issues with it