Okay, it’s fixed but I’m still scratching my head about it.
I was having an additional issue where occasionally upon rebooting the server, MySql died and I had to manually restart it.
I fixed it by following these instructions (The part under “Ubuntu 13.04 14.04 15.04 and higher with FOG 1.2.0”).
I really can’t see how that fixed it but it’s somehow working now…
So consider the problem solved. Thank you for your time.