There's a follow-up to the first mission you need to do. The campaign log should have details after you go back to her following the first mission:

Same with me: I can't pass the barrier. Though I have permission of the queen to pass it!?

Yep. Same result.

Nope, I don't see a permission slip anywhere. Can you be more specific as to where it would be?I looked to the upper left (made sure all options were showing for my sovereign and the town), down on the bar, and the upper right...and no slip.

My quest log says I have permission to pass the blockade (along with directions to to south, then east, etc), going back to her doesn't do anything. I hope tonight's patch fixes this.