w32codec-all è già installato...

Esatto, il pacchetto che mi dà problemi è proprio quello che hai indicato...k3b-codecs 1.0.4-2.1