pip install gprof2dot instala o script como gprof2dot , não gprof2dot.py .
Basta remover o .py no seu comando e você deve estar pronto.
Para referência futura: Você pode inserir uma parte de um comando desconhecido em seu prompt do shell e pressionar Tab para tentar completá-lo automaticamente (o que fiz neste caso).
Para pacotes instalados via pip , você também pode listar os arquivos que eles contêm:
$ pip show -f gprof2dot
---
Name: gprof2dot
Version: 2015.12.01
Location: /tmp/tenv/lib/python2.7/site-packages
Requires:
Files:
../gprof2dot.py
../gprof2dot.pyc
./
SOURCES.txt
dependency_links.txt
top_level.txt
PKG-INFO
entry_points.txt
../../../../bin/gprof2dot
Qualquer coisa que seja executável deve estar em um diretório bin em algum lugar.