Keep it simple. Really. There is absolutely no need to have extreme animations, or hundreds of graphic buttons. Simple text links that are positioned nicely on your page with an obvious trait that defines them as links works great.
...but the bit about a Flash-based menu system seems to counter the point about simplicity.
I think nav-problems in PBBG design stem from the fact that these games tend to be written incrementally, so features are added one at a time. Each time something new is added, the developer just sticks another link in the page somewhere (wherever it might fit), not giving any consideration to a re-design of the UI.
The biggest obstacle to motivating a redesign is not being aware one is needed. As developers, we know where everything is, because we put it there. Feedback is crucial in this case - encourage your users to complain about the interface. If you can, one of the best ways to see your interface through someone else's eyes is to grab someone who hasn't used it before and stand over their shoulder while they try it out. You'll be amazed at how obfuscated some elements of your design are - elements you thought were obvious.
Games by nature often have more complex navigation than your typical website, but it's no excuse for having a poorly organized interface. When it comes down to it, a game is just another application - so organize it like you would organize an application.