The simplest, naive algorithm to account for name changes skewing your edit-distance results would be to filter out proper names.
English is relatively easy to identify proper names and there are probably established algorithms and libraries out there for it. We used something similar using a Part Of Speech tagger a few years ago, but we were using (expensive) commercial packages. Again, there are probably other alternatives out there.
Just Then, just identify proper names like Johnny or Suzy or Barack Obama, strip them out, and run an edit distance between what's left.
There are many ways to improve results based on that basic idea - try to identify common variations in duplicates and remove them as noise from your edit distance. For example, you can match and replace known synonyms with canonical representations so that "bar/pub" or "enter/go in/walk into" would be collapsed to one representation. Assuming typos and spelling mistakes are an option, a "Did you mean..." tagger could also help.