I've never used any linux based note taking apps. I'll have to look to see what's out there...
Edit: Xournal looks like a decent app.
http://xournal.sourceforge.net/
It seems quick on my desktop, and creates a new page instantly. It saves in a non-standard format, but you can also export to PDF.
After I'm done with my current project, I'll give it a try.