[ubuntu] reason for "sudo: must be setuid root" issue on 12.04 ubuntu server

view story

http://ubuntuforums.org – Hellow, i just did a fresh install of ubuntu 12.04 - 32 bit on my vps. then i created a new user and added it into "sudo" group to allow sudo permission. then i tried to sudo to see whether it works or not. then i got "sudo: must be setuid root" warning. after googling for sometime i found out that /urs/bin/sudo file must be given chmod +s permission to make sudo work. i did that from my root user and everything seemed to work fine from then on. My question is should this issue occur on a fresh installation? everyone out there having the same issue somehow messed up thei (Hardware)