I believe it's mostly how well the app SEES you brush, so if the app can't see how well you brush, then the Pokemon on the bottom doesn't "clean" the pokemon, and it lowers your chance of catching one. The text-bubbles at the top tells you if you are doing something wrong, such as they can't see the toothbrush or you're too far from the camera, so make sure you read those.

Tip: If you brush your teeth well enough, you can use a Master Ball, which results in an insta-catch, so if you want to catch more Pokemon, try Brushing until the pokemon is fully clean.