Turns out the update didn't solve the issue. I moved my NVR away from my surround system sub woofer and also had it replaced with a different model. Not sure which one solved the issue but hasn't randomly rebooted since.
I had exactly the same issue and turned out I had to update each camera individually by going to Camera | Update and click update of each camera.
Doing an update via Maintain | Manager | Update only updates the NVR.