sudo: unknown uid xxxxx: who are you?

I was using ssh and trying to upgrade a system from Ubuntu 10.04 to 12.04. The connection had an issue so I had to login again to finish the upgrade. After running

sudo dpkg --configure -a

that was required it seems that the system no longer recognizes me as a sudoer. If I run any command as sudo I'll get

sudo: unknown uid xxxxx: who are you?

(xxxxx is for the actual id of course) and similarly running whoami will return

whoami: cannot find name for user ID xxxxx

Also when I am trying to ssh I get a permission denied (despite the fact that I am still logged in in the machine on a different session).

This means that the current UID you are using is not present in /etc/passwd. This is not a serious issue if your system administration knows what he's doing. You can check it out using:

strace -f -F -o whoami whoami

Then now you have a file called whoami, parse it:

grep etc whoami
[...]
5029  open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 3