I searched for a quite a while on forums to find the solution, but nobody seemed to know a solution. I finally figured out what it was. It seems that somehow the ownership of my startup volume's root directory (/) wasn't assigned to the root account anymore, but to my account instead. This made the kernel prelinking fail since it requires that root is the owner.
This is how you solve this after launching the Terminal app: