For any of you who are interested: I found the game that I was looking for. It
has sparkle stairways and two guards who are trying to talk to each other.
The game is called Slightly Magic. It's a PAL game, but it will work in NTSC
mode. I'm going to enjoy playing it over the holidays!