Rebuild the mailboxes if you still have some access to Mail.app (Mail.app > select the mailboxes you're working with, then Mailbox > Rebuild from the menus), or Force Quit mail if not and if mail is stuck.
The Force Quit here is different from Quit, and to Force Quit Mail.app, place the cursor over the Mail.app icon in the Dock and press and hold the option key, then click and hold on the Mail.app icon, and select Force Quit from the available options in the pop-up.
Then restart OS X.
I'd then try rebuilding the mailboxes.
Force Quit isn't something I'd recommend using as part of your daily operations.