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:
black666@starbase:~> locate libjpeg