Have you had this issue yourself and if so how long did it take to remedy?
Yes, I always try to make sure that people don't just link to the title of my page. I just send a quick email and people are usually obliged to change it, if I offer them some value in the email. Like finding a broken link on their site or a grammar error.
I found it to take a few months to come back from over optimization.