perf is a utility set added to Linux kernel 2.6.31.  It works only over Linux.

Make sure you are installing this tool for the right Kernel release. If you just type:
sudo apt-get install linux-tools
It will install it for the latest Linux release in your machine and in case you are booting a previous version (say for stability reason), it will err.

To install the correct version, for example:
sudo apt-get install linux-tools-3.2.0.43
You can find your Kernel release by typing : uname -r
To make sure it's working right you can try this: perf record /bin/ls