Mediatomb
This might help http://linuxowns.wordpress.com/2008/04/28/stream-media-from-ubuntu-to-your-ps3/
I'll be trying it later, so I'll let you know.
Also what about XBMC? I'll try that as well.
XBMC and MediaTomb were picked by my PS3 straight away. My PS3 couldn't find any files using XBMC though, it did with MediaTomb.
Trying Boxee now
I don't think Boxee streams to a PS3 as it needs UPnP? Boxee only has HTTP.
No idea how those work though.
Boxee does look excellent though. I'm loving the apps.