Game over isn't bad; in fact it is what makes a game a game - you can lose. It is the current development of people not liking to lose at a game that has made them all of the sissy-"Don't worry, I'll show a bright red arrow to show you the way and NPCs will moan what you should do next at every corner"-level (with a few notable exceptions of course).
I have had moments in gaming history where I saw the dreaded GAME OVER! or YOU LOSE! and I was still very much satisfied in stead of frustrated - as long as the gaming experience up to the game over is a heck of a lot of fun, I don't mind losing all that much. Ah I know some Age of Empires 2 multiplayer sessions where I was actually having fun getting my arse kicked. It was just a highly enjoyable battle.