This is what I found listed as PS3 compatible types
Memory Stick Video Format
- MPEG-4 SP (AAC LC)
- H.264/MPEG-4 AVC High Profile (AAC LC)
- MPEG-2 TS(H.264/MPEG-4 AVC, AAC LC)
MP4 file format
- H.264/MPEG-4 AVC High Profile (AAC LC)
MPEG-1 (MPEG Audio Layer 2)
MPEG-2 PS (MPEG2 Audio Layer 2, AAC LC, AC3(Dolby Digital), LPCM)
MPEG-2 TS(MPEG2 Audio Layer 2, AC3(Dolby Digital), AAC LC)
MPEG-2 TS(H.264/MPEG-4 AVC, AAC LC)
AVI
- Motion JPEG (Linear PCM)
- Motion JPEG (μ-Law)
AVCHD (.m2ts / .mts)
DivX
WMV
- VC-1(WMA Standard V2)
I would say use teh AppleTV or AppleTV2 preset, and see if that works. Just change the file extension in the name from .m4v to .mp4. This should work for you. I believe it uses h.264 and aac for this type of compression.