Yup, mplayer is a bitch. After my unsuccessful tries, I moved over to Xine and it's working perfectly .... ok, Xine made problems too, but in the end it was way easier to install than mplayer.
But now that I have xine up and running I'll give mplayer a shot - linux is no system for someone who gives up 
Btw: As Shotty said, what distro are you using? At Suse the package you are searching is called "libjpeg" and as far as I can tell from your output you already have them installed.
This is what I get:
Code:
black666@starbase:~> locate libjpeg
/usr/lib/libjpeg.a
/usr/lib/libjpeg.la
/usr/lib/libjpeg.so
/usr/lib/libjpeg.so.6
/usr/lib/libjpeg.so.6.0.1
/usr/lib/libjpeg.so.62
/usr/lib/libjpeg.so.62.0.0
/usr/lib/SunJava1-1.1.8/lib/i686/green_threads/libjpeg_sun.so
/usr/lib/SunJava1-1.1.8/lib/i686/green_threads/libjpeg_sun_g.so
/usr/lib/SunJava1-1.1.8/lib/i686/native_threads/libjpeg_sun.so
/usr/lib/SunJava1-1.1.8/lib/i686/native_threads/libjpeg_sun_g.so
/usr/lib/SunJava2-1.3.1/jre/lib/i386/libjpeg.so
black666@starbase:~>
Bookmarks