It seems that to encode videos for the PS3 in Ubuntu you need to use ffmpeg, however when I tried to do this the first time I ran into problems because I was using the version from the hardy-proposed software repo. To get it working you need to use the packages from medibuntu.org.

1. If you don’t have the medibuntu.org sources ready, add them:
deb http://packages.medibuntu.org/ hardy free non-free
deb-src http://packages.medibuntu.org/ hardy free non-free

As the versions in hardy-proposed are newer than the medibuntu versions, we need to force and then lock the package versions to install.

2. Run synaptic and search for ffmpeg.
3. Select the ffmpeg package, press CTRL+E, select the medibuntu version and then press “Force Version”
4. Select it again and press Package -> Lock Version. This will make sure that you don’t update it to the hardy-proposed version by mistake.
5. Do the previous steps for the libavcodec1d package
6. Install both packages

You can now use the following command to convert all files in the working directory to PS3 format videos:
find . -name "*"  -maxdepth 1  -exec ffmpeg -y -i {} -acodec aac -ac 2 -ab 128k -vcodec mpeg4 -r 24 -b 800k -mbd 2 -aic 2 {}.ps3.mp4 \;

You can change the -ab 128k to the audio bitrate you want and the same for the video bitrate by changing the -b 800k