Try converting problematic videos using a video converter such as MPeg Streamclip. This is the easiest one I know of to recommend. Handbrake is also very good as it definitely uses X264 output but not so easy to learn to use (but does include more advanced abilities than MPSC.)

To use MPeg Streamclip, drag and drop the video into the main window of MPeg Streamclip and go to File menu and choose Export to either QuickTime or MPeg-4. If QT, choose H264 format from drop down menu and select Multipass. For audio either choose uncompressed or MPeg4-AAC. Video output size should be same as original, so choose the option that gives a message saying 'No scaling will be performed.'
Alternatively from the file menu choose export to MPeg-4 and choose H264 similar to above. Then set your quality controls. And lastly click 'Make Movie'.

As for the AVI container file, yes many people still use it for the newer video formats without knowing better. MPeg-4 formats including H264 are better off inside either an MPeg-4 container (.mp4/.m4v) or Matroska (.mkv), though seems ps3 might not recognise Matroska (fixed my spelling of it lol.)

Edit: on some occasions the video had been converted into either a very odd dimension size or the video dimensions height and width ratio was incorrectly set. All video dimensions should be divisible by 16 (though X264 allows divisible by 8,4 or 2.) This is an occasion you may wish to correct the video output dimensions. For example, 320 x 240 or 720 x 560 or 1280 x 720 are all divisible by 16.

I did a google around and found this A Complete Guide to Playing Video Files On Your PS3, Xbox 3 not sure it's of any help. :)