I have "MSN only" and "Skype only" availabilities but I don't remember how I added them I think it was in the availability menu under "Edit status" but now it only allows me to edit. Perhaps there can be only 6 statuses and therefore I cannot add anymore.

EDIT: Ok, now I deleted my "Skype only" availability and then there appeared a "New status" button in the availability menu. So that's where it's done.