1) Quit Mail.
2) In Finder, press Shift-Comand-G, and in the "Go to the folder:" box, enter:
~/library/mail/V2/maildata
3) Drag the following files to the Trash:
Envelope Index
Envelope Index-shm
Envelope Index-wal
ExternalUpdates.storedata
ExternalUpdates.storedata-shm
ExternalUpdates.storedata-wal
FlagMailboxes.plist
4) Start Mail; it should tell you it needs to reimport all your Mail messages; allow it to do so.
When this process is complete, you may see Flagged messages are once again indicated, but this time when you select the Flagged mailbox you should see the messages Mail thinks are flagged, and you should be able to take whatever action you want on those messages (unflag, delete, etc.)
5) Reboot before restarting the Mail app, otherwise you won't be able to empty your trash.