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.