I apologize, but I feel the need to chime in and say that this is the exact reason I went with the G1. Despite all its faults, there isn't a phone in existence at this point that handles GMail better. I get threaded conversations, all my labels, stars, etc. The G1 has its faults, but nothing does GMail better.

I apologize, but I couldn't tell if your post was about finding a software or hardware solution to this issue. It was probably software, though, in which case I apologize again for the unhelpful response.