Acabei de me deparar com o mesmo problema. Parece que o libbfd foi atualizado, mas o perf ainda está tentando se conectar à versão antiga. Eu trabalhei em torno do problema por meio de links simbólicos para a biblioteca:
$ sudo updatedb
$ locate libbfd
/usr/lib/x86_64-linux-gnu/libbfd-2.26.1-system.so
$ sudo ln -s /usr/lib/x86_64-linux-gnu/libbfd-2.26.1-system.so /usr/lib/x86_64-linux-gnu/libbfd-2.26-system.so
$ perf
usage: perf [--version] [--help] [OPTIONS] COMMAND [ARGS]
..
Espero que isso ajude.