I only picked up the series after Dance with Dragons came out, so for long-time readers: have there been any big fan theories in the past that have either been confirmed or destroyed by novels that came out? I know Aegon being alive has been a theory for a while, and I'm sure R+L=J has been around for ages too, but neither of those is confirmed yet.

No interest in Bioshock actually! It is the combination of Sim City, Gears, Tomb Raider, South Park and probably others

One long-timer here, know the books since 2004. As far as I remember, the pretty old theories besides these ones include:

Syrio being alive;

Jeyne Westerling being pregnant of Robb's child and swapped for a double;

Tyrion being a half-Targaryen;

The great Tyrell conspiracy;

And that's about it. As you can see most of the stuff people like to predict hasn't been answered yet; GRRM seems to be reserving too much for the ending like Robert Jordan and I don't think all of these are going to see some closure.

Oh yeah I can think of two that were proven to be right: the identity of the one guiding Bran; instead of being Benjen, some correctly guessed about Bloodraven; and Theon being kept alive by Reek, though I don't think that one came as a surprise.

I think Syrio is almost certainly dead. Meryn Trant escaped alive and made no comment on the events, and Syrio was never one to run from a battle.

Westerling could well be pregnant, but that doesn't necessarily mean she was swapped.

I think Tyrion is far too similar to Tywin (his extraordinary intelligence, his skill with money, his ruthlessness, his penchant for whores) to possibly not be his son.

The Grand Tyrell Conspiracy seems very likely indeed. Olenna Redwyne is known to be a masterful player of the Game, and she's passed her skills on to Margaery (Mace being too dim to really understand them). They certainly had a hand in Joffrey's death. They are no fans at all of the Lannisters (opposed them during the Rebellion, and Renly despised them). Tywin, Kevan and Pycelle's deaths were happy coincidences, but I don't doubt that they had a hand in Cersei's arrest.

Not to mention the absurdity of the King in the North (who follows the Old Gods) and a Volantene (who either follows Rh'llor or one of the minor Essosi religions) saying their vows in front of a septon. That was a mess, but then the entire North is a mess in that show, Jon Snow included.

Yeah personally I think the Tyrells have a lot more power on the affairs of Westeros than they are showing right now. I mean, the Reach is the second biggest realm after the North and looking at its position and geography is probably the most densely inhabited of them all, if my knowledge of medieval demographics still apply here. Their potential is absolutely massive, specially now their closest rivals the Lannisters have suffered heavy losses in their family numbers not to mention the war expeditures. 

Now that the most powerful house in Westeros have started to show it's claws, but doesn't seem particularly inclined to assume power by themselves (not openly, at least) anyone willing for the Iron Throne needs an alliance with the Tyrells. I could see Margaery being widowed a third time so they can marry her to Aegon (although perhaps that would give Aegon some sort of plot armor; I mean, not even GRRM would dare to break such a nice symbolism as a woman being thrice widowed). 

Aegon seems like he's destined for Arianne now that Quentyn and Viserys are both dead. But if Dorne is willing to join his cause without a marriage to seal the deal, you could be right.

On the other hand, I feel like the current Tyrell plan is just to use Tommen as a puppet for a few more years, and once he hits adulthood, try to get a child quickly and bump him off before he becomes too difficult. I'm not sure how they would respond to having a well-educated adult king, even if he is a Targaryen. They would lose a great deal of power, and they are currently, as you said, the most powerful house in Westeros. The Starks, Greyjoys, Lannisters, Baratheons, Arryns and Tullies are all crushed, leaving only Martell and Tyrell.

Is there actaully any evidence for that rather than fans just wishing, especially after how great he was in the tv series

I like to believe most of the other theories, but I quite want Benjen to turn up, I need some closure after they have spent so long talking about him

Nope, I don't think there is except the fact Syrio was a badass and nobody commented about him after than, neither we have seen his body :/

On the other hand, it was revealed that Aerys had the hots for Tywin's wife on ADWD, not to mention his dragon dreams, so who knows about that even more awesome theory haha.

I am not sure about that, there is only so much lying about parents I can stand before I just stop believing anything that is written