having this same exact problem for quite some time on a L630, both Motion and Lumia Motion options are activated, even in MS Health the Motion Settings are activated, but still unable to get the steps counter to work.
It's funny, because, I have MSN Health & Fitness app installed, the app itself wont run (because... MS Health) but I get daily achievements notifications for reaching x% steps goal.