I have the exact same problem and it's very annoying. The subtitle appears, then disappears for a fraction of a second, then appears again to stay. It's very annoying!
Unless this bug was introduced with recent ps3ms versions I think this issue can't be fixed (looks like mencoder's bug). I noticed it with mp4 + embeded vobsubs.
same problem here. (.mkv with idx/sub inside) + when you have the idx/sub as an external file, the preferred language subs don't appear, only the default ones. But indeed, the flickering is unbearable.