I've just recently (finally) upgraded to a new MacBook Pro as of early February, and I plan on getting every last bit of value out of my AppleCare that I can. I don't think I used the previous AppleCare from my 2010 machine at all. I just got off the phone with a Senior Mail Specialist, and I'll provide my best synopsis [sorry that some of this is repetitive of this thread];
– "This is a known issue, and actively being investigated." The Senior Mail Specialist gentleman I spoke with had actually only encountered this issue just last week with another customer, so, if I'm looking at the bright side, at least it's getting more exposure. He requested if I was ok with him sending this issue "up the line," so of course I said yes, please.
– It's possible that this has some type of correlation to Gmail, as Apple began at 10.9 to try and adapt to the very unique system of mail organization that Gmail uses (labels and virtual mailboxes), because Gmail is so prominent. I do also have a Gmail account, so I can't say if that's why I'm also experiencing the problems that everyone else in this thread is having.
– One option you can try is to uncheck the Organize by Conversation option from the View dropdown menu in Mail.

– Another option you can try, in the same menu of the previous, is to Hide Related Messages.
– Another option (that I think has helped me, but it's only been about an hour) is to uncheck the "Include related messages" option (see below). Get there by Mail>Preferences>Viewing tab (third option from the bottom)

– And finally, another thing to try is to re-index your mail. Now this is the process of basically telling your computer to go back through every single message you have, in all of your mailboxes, and "repopulate the inventory," so to speak. The analogy he used on the phone was that this is similar to walking into a library and taking a totally new fresh inventory of every single item. That being said, it can take hours, even on a decked out machine. The first part of the process doesn't necessarily take so long, in which the messages on your computer are being accounted for, but the second automatic part is Mail communicating with each of the mail servers you may have (Gmail, third party, etc.), about each and every single piece of email, and that's where it gets to be time consuming. So doing this isn't bad at all (as long as you're very careful not to mess with any of the other files in your Library while doing it), just be prepared to walk away from your machine (or go to sleep yourself) for an extended amount of time. This is only on your machine, and doesn't effect any of the functionality of any of your email itself. If you happen to have a smartphone to work with in the meantime, there's that option.
- NOTE: Mail needs to be closed (quit out of completely) while you do this.
- NOTE: In your System Preferences, you need to disable your computer from going to sleep during this process.
So what you're doing is deleting the indexed files that your computer references for Mail (not deleting the emails themselves). In order to get to the index files, you have to go into your Library. In the most recent versions of Mac OS, the Library has been hidden because people messed with things that created bigger problems for themselves, and apparently the designers/engineers felt it was safer to hide this. In order to find your Library now, you need to have Finder activated. You can do this by simply clicking on the background of your desktop or click the blue and silver face in your dock

Once the Finder is active (which you'll see as Finder in the menu bar at the top left of your screen), scroll over to the Go menu. The drop down menu doesn't list Library by default.

If you hold down the option button while the Go drop down menu is open, you'll notice that Library appears. I can't take a screenshot for it, so you'll just have to try it and see. BUT, once you do see Library, follow the path of the image below to get to the folder of the items you need to (Library>Mail>V2>MailData);

In this folder, the three items you want to select are "Envelope Index," "Envelope Index-shm," and "Envelope Index-wal." Send all three to the trash, empty your trash, reopen mail, and...go to sleep? Or maybe finish a book? It's going to be a bit of time...
That's all I gathered from the whole conversation folks. I wish I had the Golden Answer, but alas, I do not. Waiting for a software update seems to be the only other option.
Best of luck!