I know this is a Nexus 7 thread but I was plagued with the same issue with my Samsung Galaxy S2. I have always used a TouchWiz based ROM whether it was official or a custom ROM as it comes with great video codec support so pretty much any video player app would play anything I threw at it. However, I have recently moved to a non-TouchWiz ROM as I wanted the Jelly Bean goodness. The only problem with this is that my favourite video player app would no longer play my video files. I tried some of the popular video player apps that do software decoding (MX Player, Vplayer) but they all had issues. MX Player wouldn't play audio and VPlayer's video was stuttery and audio/video was out of sync. I was about to give up hope and considered moving back to a TouchWiz ROM even if that meant going back to ICS but then I read this thread and gave BS Player a go. I'm so glad I did as my videos play awesomely perfect again.
I'm not sure what BS Player does differently. It seems to say I am using hardware decoding (BS Player engine) but whatever, it is working great and I love the feature to be able to speed up the video along with audio. Watching some stuff that is fairly slow paced on 130% is a great time saver and hardly makes a difference to viewing experience (depends on what you watch though).
Anyway, just wanted to convey my experiences and hopefully help someone else out in future.
