Hmm. Best I can find is this:
http://mail.google.com/support/bin/a...en&answer=7190
which states there is no option for finding unlabelled messages. Depending on how many labels you use I wonder if you might try an approach based on specifying labels and negating it so that those labels do not show effectively showing all the others?