I realize that SL is running on a massive database, but if LiveJournal can do this, so can SL.
Why not offer "rename tokens" for sale - not to change the last name, but to change the first name? Heck go whole-hog and offer tokens for first or both names, provided you choose a last name that's free in the database?
It can't be that hard to write a database search-and-replace that could do this. LiveJournal offers them for 15 bucks apiece.
Just a suggestion.