Some reason you're missing that executable. I have it on mine and according to
dpkg -S, it is part of the lsb-release package.
ned@flanders:~$ dpkg -S `which lsb_release`
What does your system say about that package?
ned@flanders:~$ apt-cache policy lsb-release
*** 4.0-0ubuntu20.3 0
500 http://ftp.utexas.edu/ubuntu/ precise-updates/main amd64 Packages
500 http://ftp.utexas.edu/ubuntu/ precise/main amd64 Packages
You can install with
sudo apt-get install lsb-release provided your apt sources are correct.