Версии:
1)Включенные автоапдейты, которые что-то такое накачали и поставили, и uid пропал (зуб не дам, но это будет вполне в стиле Ubuntu)
2)Раздел, на котором `which sudo`, смонтирован с nosuid
3)В системе есть больше одног sudo, и ты меняешь права у одного, а вызываешь - другой.