Failed to create game usually happens if battle.net thinks your character is already logged into another game, and doesn't have anything really to do with cd-key. This is generally why one character might get it abit, but another character won't.
The character that gets the failed to join, did he/she recently get disconnected from a game? How long have these "failed to join" sequences been happening? You could try to delete the bncache.dat file from your D2 directory if you wish, as it'll just be re-created when you log back onto battle.net (though whether it'll fix the problem, I'm not sure).
Edit: You can also try to delete the realm folder in your save directory too (or move it out of your D2 save folder, if you want to be extra careful).
It never hurts to delete the bncache.dat file. This doesnt sound like its your bncache.dat, just as orphan described. One thing i have noticed in your situation, is that if i join a game, rather than create, and i successfully join, then I can create after the fact. This doesn't happen often but its worth a shot.