This appears to be an issue with iOS 9.1 and up specifically, and due to a change with how motion is detected. To resolve this you'll need to go to your Phone's Privacy setting, then select 'Motion & Fitness'. Once there, turn on 'Fitness Tracking' and then The Walk should then appear as an option in this menu. Make sure you toggle The Walk on, and the next time you use the app your steps should be tracked again.
If you continue to have problems with this then please contact support at firstname.lastname@example.org