Strange issue: sudo: effective uid is not 0, is sudo installed setuid root?

[d4m4s74]

After borking my installation by trying to update xbian to beta 2 I did a fresh install to my SD card. In the installation wizard I set updating to automatic, installed the download package, and kept the rest default.
Over the course of an hour or so I set up everything the way I want it, and logged in through SSH. When closing the default xbian-config it told me xbian needed to be rebooted. After doing that and booting again instead of the default notification I got

Code:

sudo: effective uid is not 0, is sudo installed setuid root?

Using sudo for other things wasn't possible either. Since I expected it would cost me more time to figure out the problem than to just start over I reinstalled beta 2. I used the exact same configuration, logged in through SSH and got the same notification. I restarted the pi through xbian-config, and the same problem returned.
I think it has something to do with enabling automatic updating, but I'm not completely sure.
After some searching around I figured out root lost uid0, effectively making it a normal user, as demonstrated by any LS command, for example ls /usr/bin/sudo gives me

Code:

-rwxr-xr-x 1 xbian root 98712 Mar  3  2013 sudo

Since reinstalling xbian won't work, does anyone know how to fix it somehow?

edit 1: In the passwd file root is still 0 (root:x:0:0:root:/root:/bin/bash)
edit 2: maybe it helps, the only difference I found that might mean something is that before the forced reboot /etc/fstab didn't have a line for /, but after it does. Unfortionally I've already reinstalled xbian so I am unable to check what removing that line does