Ok, so those of us who never purchased extra slots, just got them as vet rewards and whatever (I had 4 extra, one in use) still have to rely on the online store to use those slots? I just logged in a short time ago to build a new toon under the new i18 content only to find my slots were all gone (US servers).
Can't say I'm surprised that this relies on the online store functionality, but at the same time, as a programmer myself, I have to say that this is kind of a poor design choice. It should've been easy to modify a players account on the game server to say something like "this account holder has purchased X number of character slots" and then they'd always be available, instead of the Game server having to ask that question of the Store server everytime a player logs in to the game (or relogs if switching toons). That's too much extra overhead in code and traffic, and I wouldn't have done it this way. Better to mod the user account to show the extra slots purchased at the time of purchase, and save the cross-checking for a once a day routine, instead of every single login attempt.
In other words: I suggest a code rewrite to fix this, and I'd put something in the Known Issues page to cover this so that all players are aware.