Design your application differently so that instead of app states doing a bunch of stuff on their update methods that depend on other app states... they register themselves with their dependent app states (say a network listener, physics listener, etc.) and thus that part becomes part of the other app state's life cycle.
In general, it's a bad idea/design to rely on app state order for anything but making sure it's there when you want to grab it. Otherwise, your life is going to be so much easier if you design your app states to be decoupled. Either this means combining things (like why is the network updating separate from the connection management?) or go with the listener/strategy registration approach.
Also, another thing to consider and the more common way I guess is to make sure that dependers clean themselves up on disable but resource holders clean themselves up on cleanUp(). They are generally longer lived anyway.
So for example, it's ok that I have a bunch of app states the depend on the EntityData object I create in my first app state because they all stop doing anything after onDisable() is called. The EntityData state only destroys the entity data when actually terminated.
That's sort of the lifecycle of app states, anyway.
initialize() setup my resources
onEnable() start doing things if I do things.
updatE() do the periodic things I need
onDisable() stop doing things, clean up my listeners, etc.
cleanup() free up my resources