I too have a Pokéwalker, and it is indeed difficult to get it to register steps the right way. It all depends on the rhythm of steps and the exact "arc" of motion.
Try clipping your Pokéwalker on different locations on your body whenever you're walking/running/jogging/etc. and see how effective it is. There are a few places that work fairly well and other places that are not so effective.
Examples: ankle of your pants; front or back pants pockets; shirt sleeve; belt.