Did you try to raise the bitrate?
500k bitrate seems a bit low for the 30fps video. Can you do it at least 2000k (if your video 720p) or at least 3000k (if your video 1080p)?
Yes, I've had it much higher, over 10000k - I just happened to pick 500 when I did the test for purpose of screenshot. In all cases, it still defaults back to 25 fps.