Você precisa ter ambos linux-tools
e o kernel em a mesma versão ou não funcionará:
sudo apt-get install linux-tools linux-generic
sudo reboot
Se você estiver usando kernels da linha principal, você deve compilar o perf em relação às fontes da linha principal, caso contrário, ele não funcionará .