I'm encountering something similar...I transcoded my video file with the Handbrake PS3 setting. Nevertheless, streaming did not work. Then I copied the file from my external HDD onto my MacBook and started to stream it again - it worked.
I don't know but it seems that it does matter WHERE your MP4 files are saved. There seems to be a difference whether it is saved on the internal PS3's HDD, on an external HDD attached to a Mac or on the Mac's HDD itself.
Maybe it has something to do with the WLAN configuration...