I know that this is not a bug per say, but it is (in many peoples opinions) broken game play.
Please remove the names of deleted characters from the database of taken names.
One of the hardest parts of playing this game is coming up with a name that has not already been taken.
-Neurosinth, Beurocrat RK2