Comment 9 for bug 289264

btw: I've added the following snippet (in variants) to debug this (and added output to update-notifier-kde):
(update-notifier-kde &); sleep 5; pid=$(pgrep -f ^python.*update-notifier); echo $pid; for i in `seq 1 50`; do ps aux|grep update-notifier|grep -v grep|grep python|awk '{print $2":"$5"/"$6}'; sudo touch /var/lib/apt/lists/; sleep 15; done; kill $pid

This may help you, apart that a "real profiler" is more useful of course, see e.g. http://stackoverflow.com/questions/110259/python-memory-profiler