You need to sign an address which you posted with that account, and send it to cyrus. Look at the sticky in meta for the guide. Don't expect a reply any time soon though, as loads of people are requesting the same thing so he likely has a backlog.
I've got the same issue. Really annoying that the message says to email, but not that this procedure is in place. I didn't couple my bitcoin address, so I've got no way to recover. Any suggestions on other ways of proving ownership? Btw. My email address never changed, shouldn't the database confirm this even after the hashes got stolen?