Since it's only happening on certain videos, it sounds like an encoding problem when the video was made. If the videos don't play well on a PC either, then it must just be those videos. Might not be anything you can do as your phone plays other videos fine.
Can you post a link to one of the questionable videos so we can test on PC and Android? Might help you verify if the problem lies with your phone or the uploaded videos.