Another of those “I couldn’t find the answer on Google so I’ll write it here” postings.
By default, Thunderbird only checks your Inbox for new messages (which stems from a POP3 legacy). If you have server-side rules (or use a web interface to do your rules), then you’ll want Thunderbird to check subfolders as well. This can be done by right-clicking the folder in question, selecting properties, and ticking the appropriate box. There’s no(t yet an) option to do this globally.
Applies to Thunderbird 0.9.
Update: April 2008
Years later, even with Thunderbird 2.0, this is still a problem. But there’s now a global option, thankfully. Although it’s completely hidden, it saves a lot of time if you’ve got lots of subfolders.
Open up the preferences dialog (either Tools -> Preferences or Edit -> Preferences), and click Advanced -> General -> Config Editor. In the filter box start typing ‘mail.check’ and then double click on mail.check_all_imap_folders_for_new. It should then change the value to true (and it’ll appear in bold since you’ve changed it) and all should hopefully be hunky-dory.