A few things about this.
The remove topic code is not slow per se, the problem is that we
select All after doing the removal, and it's selecting All what is slow :)
In my box selecting All with ~250 nodes takes about 3 seconds (1,4Ghz
box), which is clearly too slow.
After doing lots of profiling and going crazy about this, I asked kris
about it and it resulted that it was a gtk+ bug after all: 
"Massive inefficiency in gtk_tree_model_sort_level_find_insert()"
http://bugzilla.gnome.org/show_bug.cgi?id=109292
With that patch applied to gtk+, you'll enter in a new world of
extreme performance.
So now the question is, while we wait for this to land in gtk+ (it
will go to HEAD, but kris is afraid of backport to 2.2.x, as the
GtkTreeModelSort is very fragile), what do we do?
There is a huge and messy workaround for this in Rhythmbox, but I
think the best approach is simply don't select anything after topic
removal (of course this does not fix the fact that selecting All is
still a pain, but I think it's worth to wait fot the gtk+ fix).
What do you say Marco?

I implemented a workaround for this in cvs. Now, before removing a
node we select the next node in the view, the previous one if it was
the last one, and nothing (All) if it was alone. I think this makes
impossible to select All when deleting a topic (Most Visited and Not
Categorized, which can't be removed) are after it), so I'm closing as
fixed.

*** Bug 111183 has been marked as a duplicate of this bug. ***