Se o seu provedor de pacotes não produziu um método setup.py uninstall , na maioria das vezes, você pode remover manualmente o pacote do diretório site-packages do seu Python.
Isso estará localizado em /usr/lib/python2.5/site-packages ou equivalente para sua distro e versão do Python. Dentro disso, haverá um diretório ou um arquivo .egg correspondente ao nome do pacote. Basta apagar isso.
Existem alguns casos em que os pacotes instalam coisas em outro lugar. O Django, por exemplo, instala django-admin.py to /usr/sbin . Sua melhor aposta é executar setup.py install novamente, anote o que está instalando onde e depois a limpeza.