Ok - I did this yesterday.... so let me see if I remember how.

Go to "Quick Links"

Then "Private Message"

And there should be some buttons you can click on (up top) to clear all as read or to delete all of them.... I deleted all of mine and started new.

Hope this HELP.