Have you got all the repos eneabled .. such as universe, mutiverse, independent, and canonical partners ?
Have you tried reinstalling libk3b6-extracodecs
sudo apt-get install --reinstall libk3b6-extracodecs
pooky2483@pooky2483-ubuntu12:~$ sudo apt-get install --reinstall libk3b6-extracodecs
[sudo] password for pooky2483:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
libsvga1 libvdpau1 computer-janitor
Use 'apt-get autoremove' to remove them.
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not upgraded.
Need to get 0 B/28.0 kB of archives.
After this operation, 0 B of additional disk space will be used.
(Reading database ... 270708 files and directories currently installed.)
Preparing to replace libk3b6-extracodecs 2.0.2-3ubuntu4 (using .../libk3b6-extracodecs_2.0.2-3ubuntu4_amd64.deb) ...
Unpacking replacement libk3b6-extracodecs ...
Setting up libk3b6-extracodecs (2.0.2-3ubuntu4) ...
Doesnt come up with install the mp3 stuff now, don't know whether it's due to telling it not to notify me or what I've just done in re-installing the restricted extras but the mp3 plugin is not there in the list as in the post where I show the list of plugins...