One of the best tools for profiling I've used with python is gprof2dot, which analizes cProfiles output and generates a function call-graph that gives deep insights as to what is really taking execution time.

It can help you see a lot clearer why things are slow. Though it has its nuissances, it significantly improves your understanding of where time is spent. It's the same data from cProfile, but much better organized.

That tool, combined with the line_profiler (kernprof) can work wonders.