Huge plans indeed, but man, Shadowgate! I played that on the original GameBoy. The breadbox, we called it! Well no harm in trying, I daresay it can be done- though usually people start learning AGS (an Adventure Game engine) by making a small adventure game
But Shadowgate! I liked that game!
I doubt anyone here will be mad at you or so, but maybe nintendo will be 
About the "rules regarding remakes": That has always been a bit of a shady zone. The minute you start using original assets you are infinging copyright. Even using an existing brand (like Space Quest) and creating your own assets is... tricky, and I know of at least one promising game having a chease and desist being fired at it. But often the companies that made those games are no longer existent, and things just.. you know, work out.
selmiak is right though: Nintendo is known to protect its brands. But for such an old game, well, I really don't know if they'd care very much.
Anyway, long story short, best of luck and happy game-making!

*goes and digs out his old GameBoy*