I wrote a FSM based off of a chapter in "Massively Multiplayer Game Development" Edited by Thor Alexander. Inside is a chapter labelled "Parallel-State Machines for Believable Characters". This is written in python, but the concepts are easily translatable into C++. I highly recommend checking this out, even though this is about character states, not game states.
What I created is here: https://github.com/swganh/mmoserver/tree/develop/src/ZoneServer/https://github.com/swganh/mmoserver/tree/master/src/ZoneServer/GameSystemManagers/State%20Manager look under StateManager for implementation details, but basically you have different 'base states' that you can use. Then from there you have the specific states that you transition to as a character, so every state is a class. You then check if can transition from one state to another and then on 'enter' you make your switch, you can also easily do things like put in events after moving to a state. I found this worked out really well for the game so far.
What I have implemented is what the book calls a parallel state machine, which is essential multiple fsm's working together, in this case you can transition into one state, that blocks all other states (ie: CreatureState_Dead). I'm not going to go too much more into detail as I don't think it would really help you, but if you'd like I can elaborate.