Tomboy is a nice app. It's very speedy and it's non-hierarchical, if you like that (I do, but your machine has to be fast enough to handle rapid searching).
A more traditional notetaking app is Tuxcards.
I believe there are quite a few tree-style outliners and notetakers. Have a look at
http://www.linuxsoft.cz/en/.
The best I've found in the non-hierarchical category is Notelens, a .Net app that currently runs only on Windows. Tomboy approaches Notelens in usability and concept, but isn't quite there. However, Tomboy's free and Notelens isn't. I sometimes run Notelens under VMWare, though I'm using Tomboy more and more.