I think you need to go see the king for a quest (might be wrong though). Check the castle or wherever you last saw the king.

I'm not sure just where you're at - which zones you need to open.
How many of the six zones that are from the last update do you show are still locked up there to the left of Twiggy Lake? All six of them, or just the last two that are at the very top?

I think you need to finish up The Lost Halls Relic Quest. Those six zones don't all open up at the same time. You are at a high enough level to open the first four, so that can't be the problem for those ones. The last two, at the very top next to Twiggy Lake are not accessible until you reach Level 130, and are all caught up on The King's Quest. There's a King's Quest in-between Levels 110 and 130, ending with finding the Unicorn, which you've already done. (Trying to think as I go... having a hard time remembering the details.) In order to open up the first four, you have to have all of the prior content Quests completed, including The Haven Crypts, which is where your last unfinished Quest is. To start with getting those first four zones open, you also have to be completely finished with The Desert City area (which it sounds like you are), then you need to go to The Ruined Outskirts and talk to Billy to start, and finish, a Quest for Billy to open the first four. Billy sends you on a Quest to find Chuck in The Secret Alley, which should be one of the zones that are locked now, it's the zone directly to the right of The Palace Steps - when you get to The Secret Alley, just click on the locked gate to the East and see if the gate opens if you just try to walk through it - I remember somebody saying that somewhere, that they just clicked it, but I'm not positive if that's true. Chuck in The Secret Alley has a blue ! when you get that zone open, they're new daily repeatable Quests, but it will not let you do them right away, you have to complete a different Quest for him first. After all of that, you need to get to Level 130 to open up the last two zones.
If you have any Quest icons under your Level/XP bar, especially the one for the King's Quest, click them and check out what they're saying you need to do, and double-check your Quest Log using the yellow ! at the bottom next to your map icon for info too.

Check out these two threads that are here on the Forum. Justin comments about these zones quite a bit in them.
The first one is his post announcing the update that brought out those six zones: http://forum.djartsgames.ca/?thread_id=904&page=1
This second one is Justin's announcement about The Haven Crypts update, which was the one right before that last one: http://forum.djartsgames.ca/?thread_id=77&page=1

I really can only think that it must be because you need to finish that Lost Halls Relic Quest, and also need to go talk to Billy. You only had to be at Level 110 in order to be able to open those first four zones, so that isn't it either. I hope that I didn't confuse you, and that I helped in some way. Maybe this will jog someone else's memory on it too, and hopefully correct me if I'm wrong on any of this.
Good Luck!

Yay! Good deal.
I wanna take a poll to see how many people got stuck on that Billy part! :)