Seems like your sources.list is wrong.
mcc@dcerouter:~$ apt-cache policy mplayer
mplayer:
Installed: 2:1.0~rc4.dfsg1-2yavdr0~lucid
Candidate: 2:1.0~rc4.dfsg1-2yavdr0~lucid
Version table:
*** 2:1.0~rc4.dfsg1-2yavdr0~lucid 0
500 file:/usr/pluto/deb-cache/ ./ Packages
500
http://deb.linuxmce.org/ubuntu/ lucid/beta2 Packages
100 /var/lib/dpkg/status
2:1.0~rc3+svn20090426-1ubuntu16.1+medibuntu1 0
500
http://packages.medibuntu.org/ lucid/non-free Packages
2:1.0~rc3+svn20090426-1ubuntu16.1 0
500 mirror://mirrors.ubuntu.com/mirrors.txt/ lucid-updates/multiverse Packages
2:1.0~rc3+svn20090426-1ubuntu16 0
500 mirror://mirrors.ubuntu.com/mirrors.txt/ lucid/multiverse Packages
That should be coming from us. Can you post your cores /etc/apt/sources.list please? I am assuming that this was a net install. I guess I am also assuming this is a 1004 install.