I doubt I would need to change my name, but I think it's a great feature that you should try to keep if possible. On other sites, there are people who delete their accounts simply to change their user name, but Newgrounds gives users the flexibility of changing their names whenever they like.
What exactly worries you about the dead links? The problem would be when users themselves post links to their userpages on forums, reviews, author's comments, or other similar things. But if users can do that for other websites as well, and when those websites change the link becomes a dead link. It's to be expected whenever you allow user input on the site.
If you're worried about Newgrounds having problems when you make links to the user pages, that wouldn't be a problem. You already allow us to have signatures for forum posts, and whenever those area changed, they're changed across the entire site. You could do the same with user pages.
I reccomend putting a warning when people change their name though. Something like, WARNING: The URL of your user page will also change to match your new user name. If you have posted a link to your user page on the forums, in comments, your own personal site, or the like, these links will become un-functional. Maybe not a prompt though. That might annoy people.
Perhaps you could make user pages that have the user name in them optional, or make the user name user pages redirect to one that uses a number. It would give people a little more flexibility.
Good luck finding a solution to this dilemma, Tom.