I am not a lawyer, and this should not be considered legal advice (sorry, gotta cover my ass), but here is my understanding of the whole thing:
From a legal prespective Zelda Classic is NOT perfectly legal. Strictly speaking, it infringes on the trademark "Zelda" and the copyrighted first and second quests. However, from what I have seen Nintendo has unoficially turned a blind eye to ZC.
ZC is NOT a ROM, it is a full from-scratch clone of the original game, with many features added as well, and cloning a game engine without using the original code is perfectly legal.
Therefore the game engine itself is perfectly legal to use and develop completely original quests for, but the original quests, strings, and graphics are copyrighted by Nintendo. Any other ripped graphics such as the Chrono-Trigger tileset, the BS-Zelda tileset, and the Warcraft and StarTropics tilesets that I have made, are copyrighted by their respective owners (e.g. the Warcraft graphics are copyrighted by Blizzard Entertainment).
This sort of copying is done purely out of love for the original game, and because there is no profit involved and the games are very old companies tend not to care.
The other legal issue that I am aware of is Trademark. "Zelda", "Link", "The Triforce", "Ganon", and possibly other phrases used in the game are trademarks of Nintendo. Trademarks are meant to guard a company's business from imitators, and ZC certainly is an imitator. To be completely legal in that respect AGN would have to remove all references of trademarked terms, especially "Zelda".
However with over one million downloads of Zelda Classic 1.84 on downloads.com Nintendo cannot possibly be unaware of ZC. But Zelda Classic costs them nothing in lost sales, does not make AGN any money, and helps grow a devoted fan-base. I personally doubt they would bother doing anything against ZC.
In short, Zelda Classic is more legal than a ROM that you could download. It's not perfectly free and clear, but I don't have any real reason to believe that Nintendo would go after the people who make it, let alone the people who use it.
Regards
Gordon