Gmail: can't create message labels?

That's weird. When I look at my Gmail messages, the drop-down More Actions... menu contains: Mark as unread, Add star, Move to Trash, a dashed line, my existing Gmail label, and a link "New Label...".

Ah, well, there's a different way to get to this same feature anyway.

On the top right of your Gmail window, click on the blue Settings link, then click on the Labels tab. You should see something like this:

Type in the name of your desired label, click "Create", and you should be ready to go with that label. Further, I bet the Actions menu changes to reflect your use of labels too.

One useful trick for labels is to use them with Gmail filters, as detailed in my article Forward selected messages from Gmail.