First off... it's not Magic Sword, but it's a pretty good basis to start from. The game was a similar side-view platformer, fantasy themed, where you could choose from a few types of characters at the start. I seem to remember a female archer, a robed wizard, and I'm going to guess that there was a male fighter to round it all off.
It wasn't as fast paced as Magic sword, you could play two players at the same time and you could get new weapons like a fire throwing staff if you were the wizard character.
I remember starting from a village, adventuring outdoors and quite quickly encountering a waterfall style level. There were traps and enemies.
I've played Magic Sword and just checked a video walkthrough of the game to ensure that its not the game.
Any help here would be appreciated!