I have the premium version and I have created 2 labels. However when I try to create additional labels (via Edit Tasks - Attach a Label - Manage labels - Add a new label) the screen goes back to the 'Today' view.
Unfortunately, I can't reproduce this issue. Following the steps as you've described, it all works fine and I can add labels this way. Please tell me what browser do you use and if you can reproduce this issue in another browser.
Also, please note that you don't have to go through these menus when adding a new label that you haven't used before. Instead, you can simply type it in after the @ sign right within the task's name, for example @next @delegated @home etc. If it hasn't been used, it will be created automatically upon first use.