The Gmail [advanced search][1] help page says:

label:	 Search for messages by label*  
***There isn't a search operator for unlabeled messages**

Example: from:amy label:friends   
Meaning: Messages from Amy that have the label "friends"  
Example: from:david label:my-family  
Meaning: Messages from David that have the label "My Family"

Sorry!


  [1]: http://mail.google.com/support/bin/answer.py?answer=7190