Take a game where you get to pick a single number between one and a billion. If you pick 10 you win. This has a billion states, but it's trivial. I can increase the bound above a billion, it doesn't matter.

State count gives an upper bound, though, to how complex a game can be, for sure.