Perhaps your hardware debouncing is not working? What circuit are you using? Typically you need a debounce filter of around 50 to 100mS. If possible, check that a clean switch output is present at the processor input.
Another possibility may be that your code has a race condition where it doesn't wait for a switch edge and instead is triggered by the switch level. That could be getting you into trouble.
If you know what a state machine is you really should look at implementing your logic as one. I can see basically four states. Once you implement the state machine, it will be obvious what's happening -- assuming the problem is in the software.