Yeah, I thought that either his "little birdies" were literally little birds, or that he may see through other young telepathics. Still could be the latter if he were the most powerful warg in the world and therefore could see through humans (only a certain kind? Only prepubescent? Which could explain his castration.. which leads to another point I brought up last season...) Eunichs were often made eunichs to enhance their perceived magical powers. For example, in many cultures, it was not uncommon to castrate shamans and priest, and the like.

So yea, I think it's a lock that Varys is magical, and now that we know about wargs, I'd say there's a strong chance he is one.