Erratic State Behaviour

The quickest, most reliable way to cure this problem is probably to use T/F variables instead of states to track completion. Moodle is a frequent theme of funny occurrences here, and a minority of students could have funny settings, or be doing funny things. Variables are pretty much immune to funny stuff.

Whatever action returns them from each location should (before it returns) set a variable that means that location has been visited. The main slide should be set to return to initial state on revisit. (That restarts the timeline.) When the timeline starts on the main slide, the variables are checked one by one. For the ones that are visited, the corresponding box is changed to Completed state. (Using Visited state can cause conflicts with the built-in triggers when the box is clicked.) Then if all the variables are true, the next button is enabled.

For a sample, check the mixed Navigation in the sample at this post:
https://community.articulate.com/discussions/articulate-storyline/free-sample-restricted-and-free-random-navigation-using-variables-and-triggers 
It has four buttons that take the learner to different slides, and when they are all visited, a button appears that can be used to advance. In the restricted navigation, the four buttons appear in order, only after the previous one is visited.

I think this will correct the problem without you having to find out what it is.