I found out that it's a bug from the media server: when you have several movies and subtitles with similar names, it will not always get the correct subtitle.
For example in my case I had 4 videos and 4 subtitles:
When I tried to play the first three movies, it looked like the subtitles were out of sync, but in fact they were using the wrong file. The file Heroes.S03E03 was using Heroes.S03E04 subtitles, Heroes.S03E04 was using Heroes.S03E05 subtitles, and so on... The last one was not getting any subtitles.
When I play them in the computer, every single one is playing the correct subtitle, so my guess is it must be a ps3 media server bug.
The Workaround I found was, putting every single video and subtitle inside it's own folder. Using this workaround everything played fine until now for me.
Hope this helps everyone with the problem.