Ok, here's what I did. Included in this post is a zip file with two folders.
1) One includes all of the RPM files that I personally needed to get rid of all of the dependencies.
2) The other includes a replacement yum.conf file to be placed into /etc under the file system (Make sure you're root when you do this, also make sure you backup your original yum.conf)
Simple (somewhat) directions:
1) Replace yum.conf with included yum.conf. This adds a few new servers to your database (they point to yellow dog linux 4.0 servers though, so remember that in a few weeks or whenever freshrpms updates so you can modify the files again)
2) Go into your terminal and type these commands as root (or type su to gain root privileges):
rpm --import http://svn.rpmforge.net/svn/trunk/rpms/yum/RPM-GPG-KEY-freshrpms
rpm --import http://svn.rpmforge.net/svn/trunk/rpms/yum/RPM-GPG-KEY-yellowdog
3) Ok, now for the confusing and possibly frustrating part. As I said I'm new to Linux so I had no really great way to do this. What I did was randomly click the RPM files and move them to another directory as they successfully installed, if I received a dependency error, I'd find the file that I needed and go to install that one. It doesn't take too long.
4) Finally, install the VLC included in this package.
I've been able to play every mp3, xvid, divx, mpeg, etc that I have thrown at this. Also remember the tip that the first poster mentioned (start up YDL in the gnome interface or else VLC isn't going to show up under applications).
Also, remember I'm really new to Linux myself, so I'm not going to be able to answer many questions. Everything that came out of this was due to trial, error, and a lot of searching.
Yeah I know that it's a bit silly that the whole thing is bunched up in a zip, but I'm assuming you have a way to transfer these files over to your PS3, whether it be a thumb drive or your Ipod.
Good luck everybody.
Here's the link. I hope megaupload is fine - I tried to attach the file and it errored out twice and I'm tired and rapidshare was being slow. If megaupload sucks too badly, I'll throw the file up on rapidshare tomorrow.