Подскажите инструмент, который покажет, сколько исполняется каждая функция, строка и т.д. и нарисует мне временные диаграммы?
Обязательное условие: умение работать с потоками.
Т.к. у меня чувство, что тормозит именно синхронизация.

Встроенным не пробовал?

http://stackoverflow.com/questions/653419/how-can-i-profile-a-multithread-program-in-python
http://stackoverflow.com/questions/653419/how-can-i-profile-a-multithread-program-in-python/653497#653497

Ну это все код… а ничего такого IDeшного красивого нет?

Есть, в гугле легко находятся.
Только зачем?

easy_install runsnakerun