I can't speak specifically for console, although I can't imagine it'd be a problem there, but on PC/Mac it is entirely possible to reuse old names. In fact, you could delete a character with the intention of creating it differently but using the exact same name you deleted not 1 minute earlier. So far as I would imagine, this would also ring true for consoles.