Could someone tell me what a 'Skull' on a card means?
I was told that such a card isn't tournament/standard legal.
The card in question is 'Quiet Brothel' from Circle of Spies
Correct. A "skull" symbol on a card (pretty much anything from the Wildling Hoarde and Circle of Spies promo decks) means that they are not legal for tournament play. Period.
Really? I thought that the Personal Guard could be used because he was reprinted as a promo. I also thought the same was true for one of the Varys copies. Is that not the case?
Depends on how strict your TO wants to be. Strictly speaking, your skull versions are illegal, even if they are otherwise exact reprints of standard legal counterparts (like Personal Guard). Most TOs aren't that strict, but they could be if they so chose.