The non-free codecs distributed by Medibuntu now come to a single metapackage: non-free-codecs. The proper package matching the architecture will be installed (please see the Launchpad bug report below).

Just add Medibuntu repository to your sources.list:

# Medibuntu. deb http://packages.medibuntu.org/ gutsy free non-free

Add the key to your keyring, reload the sources.list file and install the package: