At the Gates: When revealed, if you have no City plot cards in your used pile, search your deck for a Maester character of printed cost 3 or lower, and put it into play. Then, shuffle your deck.

Fear of Winter: Each player cannot play or put into play more than 1 card from his or her hand until you reveal a new plot card.

FAQ page 13: Character, Location, and Attachment cards are “played” from the hand during the marshalling phase, by taking a player action and paying their gold cost. Event cards are “played” by placing the card on the table, paying the specified cost, and triggering the effect. "Put into play" effects are not considered to be "played." Similarly, when a card is "put into play," it does not trigger any "when played" effects, and vice versa. Both, however, would trigger effects that occur when a card "comes into play” or “enters play.” "Put into Play" is a game mechanic that bypasses all costs (including all gold penalties) and play restrictions.

So...does the card arising from At the Gates count as being played from the hand, or from the deck? We had played it as coming first from the deck to the hand, and then from the hand into play, meaning that it is the only card that can be played due to Fear of Winter (this is what my opponent said although I have my doubts based on the above wordings).

Further, as per this thread:

http://www.agotcards.org/card/v/600

They are saying that the card comes from the deck, not the hand, and therefore does not count. I would tend to agree with this.

I would appreciate if someone could refer to the relevant rules/FAQ section to support any advice given, thanks!

There is no specific FAQ entry, because it isn't needed: Fear of Winter's limit doesn't apply to cards put into play from anywhere but the hand. At the gates never mentions the hand: the Maester starts in your deck and ends up in play, so your opponent's reasoning is deeply flawed (and sounds like wishful thinking). If an effects moves a card through your hand, it will say so, or at least mention drawing it (like Val).

Thanks a lot pal! Then I think my opponent was being generous, since it was my FoW against his AtG

You're welcome. And it seems I was a bit too ready to assume the worst about your opponent, so I apologize.