When an email client arbitrarily adds a "Re:" it messes it up.
I'm pretty sure Thunderbird uses the Message-ID and In-Reply-To headers to create the threads, not the subjects. But some people don't always use the Reply function, or Reply to an old email when they want to start a new conversation. Maybe Gmail has some logic to get around these limitations.
In Thunderbird 3, we use a combination of the two models, as some mail providers (Yahoo! for example, IIRC) strip away the right headers. Thunderbird 3's threading is way better than Thunderbird 2's.
I'm pretty sure Thunderbird uses the Message-ID and In-Reply-To headers to create the threads, not the subjects. But some people don't always use the Reply function, or Reply to an old email when they want to start a new conversation. Maybe Gmail has some logic to get around these limitations.