nvm...didn't understand how this worked but apparently I just needed to unlock it with server slot 
. I was afraid to try that because I didn't want to accidently use a global slot...derp
I believe this is working as intended. When you go from VIP to premium, all your characters are locked, and you should also receive an appropriate number of slots with which to choose the ones you want to unlock.
Edit: OK, glad you got it figured out.
My VIP sub was up today and I was a tad late getting it payed. I logged into my account and now all of my toons are locked again. Before going VIP about a month ago I used my awarded unlock tokens on some of my older toons. Once I went VIP I noticed that those I unlocked were still unlocked, but all of the others were still locked. I honeslty didn't have a problem with this because I didn't play many of them, and liked having a bunch of new slots to make new toons. I figured I could always pay to unlock any old toons should I decide I wanted to play one in the future. Did I screw something up by unlocking those toons before hand? I have sent a message to support, and I am hoping it is not an error on my end. Any help/suggestions is appreciated thanks!