ZPavelZ: Must be Landstalker: The Treasures of King Nole
http://store.steampowered.com/app/71118/
The hair color is different, but the rest including the faerie matches well.

Magnitus: As I recall, it was really a 2D sideways platformer (like Mario or Megaman at the time).

All the action was happening on a 2D plane (forward, backward, up or down).

Magnitus: That I played as a kid.

I have fragmented memories of it which occasionally resurface and the nostalgia factor is driving me insane.

Basically, it's a platformer RPG.

You control 1 protagonist that has blue hair and usually is equipped with a sword & armor (though I vaguely recall some underwater parts where you have a trident).

You have various sidekicks traveling with you at various parts of the game (in particular, I recall a faery in the early game and a miniature dragon in the late game).

In at least one part of the game, you have memorize some tune and type it with your control pad to move forward.

The game is non-linear (ie, you can backtrack to various parts you previously visited in the game) and this comes in handy to solve some puzzles.

That's about as much as I recall atm...

Garugo: Is it one of the Wonderboy games?

http://www.futuregamez.net/special/update10/wonderboy3.jpg

Magnitus: Yes :).

Glad to see that some traces of the game can still be found somewhere...

http://www.mobygames.com/game/genesis/wonder-boy-in-monster-world

Probably a so so game in retrospect, but there is something to be said about fond memories.