So, was the problem that the server was full? Sometimes if you wait until off hours, the server load goes down enough to let you create a new character. Unless the server's marked as congested or locked, then you might be SOL.