That is The Fairyland Story. When I was a kid, mom and I stayed at a hotel that had this game and the Willow arcade game. The Willow Arcade game is shocking hard, so I played a lot of Fairyland Story. I loved it and almost beat it. However, I never made it back to that hotel and the name of the game was lost in obscurity over the years. Much like a summer romance, I thought we'd never meet again, but...but....DESTINY INTERVENED!!
Yesterday I purchased Taito Arcade Classics 2 on a whim and one of the 35 games listed was "The Fairyland Story." Turns out I suck at it now, but I'm working on getting better again. GLEE!!