A solution to this some services have used is to have a separate username and display name. Your user name is your portal to the site; what you login as, what your URL is based on (usually), and sometimes how people find you.
Twitter is probably the most relevant solution, as they have good SEO but they do have a display name you can change. You can't change the name most users know you by, but if the user's real name changes the system works fine, and people can search for you by your real name (though your user name is much easier to find, especially in search).
Update: Apparently twitter does let you change your username and your URL, however your followers continue to follow you after the name change. Thanks to JohnGB and Daniel Newman for correcting me. I'm not sure I like Twitter's solution as much any more, but it allows the user the freedom.
Steam implements this such that your username is a secret you use to log in, and friends always find you by your display name--which can change at litterally any time. Personally I've found this extremely annoying as half of my friendslist changes names once a week. Steam lets you see all the names you've seen a friend use before, but still note that this can make it very difficult to know who is who if your users change their only display name often.
Skype has user names which you use to find people, and then display names within the application only. Skype calls this your "real name" but as you can change it at any time many people change it to their favorite movie character, 4chan meme, ect. This is an interesting set up as you can always find someone by their user name, but like with Steam I've often found it difficult to determine who the heck half the people in my friends list are without viewing their profile.
Steam and Skype may be less relevant to your site (I assume) than Twitter, but remember that URLs aren't the only things that change. It's important that Google can find Joe Soap, but it's arguably more important that Joe Soap's connections on your site can find the person they met as Joe Soap. Facebook has fairly nicely avoided this issue with their environment of "real names only" and rather aggressive application of that policy, but I wouldn't count on that to work on another site.