Consegui corrigir este mesmo problema no Linux Mint 13 (baseado no Ubuntu 12.04) fazendo o seguinte. Você já tentou isso?
Mova os arquivos de configuração e banco de dados do diretório ~ .mediatomb:
sudo mv /home/<user>/.mediatomb/config.xml /home/<user>/Desktop
sudo mv /home/<user>/.mediatomb/mediatomb.db /home/<user>/Desktop
sudo mv /home/<user>/.mediatomb/mediatomb.db-journal /home/<user>/Desktop
Em seguida, iniciei o Mediatomb e deixei recriar um arquivo de configuração e banco de dados padrão. Eu adicionei um diretório através da interface web e ele começou a funcionar novamente. Então eu desliguei e copiei informações relevantes da minha configuração antiga para a nova (eu especifico quais diretórios importar / assistir no arquivo de configuração ao invés da interface web - então copiei isso) e até aí tudo bem. Havia algumas diferenças entre os novos e antigos arquivos de configuração, então presumo que houvesse uma discrepância em algum lugar. Aqui está o meu novo arquivo de configuração (em funcionamento) caso ele o ajude:
<?xml version="1.0" encoding="UTF-8"?>
<config version="2" xmlns="http://mediatomb.cc/config/2" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://mediatomb.cc/config/2 http://mediatomb.cc/config/2.xsd">
<!--
Read /usr/share/doc/mediatomb-common/README.gz section 6 for more
information on creating and using config.xml configration files.
-->
<server>
<ui enabled="yes" show-tooltips="yes">
<accounts enabled="no" session-timeout="30">
<account user="mediatomb" password="mediatomb"/>
</accounts>
</ui>
<name>media@Mintop</name>
<udn>uuid:c0bc3ac1-d8aa-45b4-9520-d503cc1a92e2</udn>
<home>/home/mike/.mediatomb</home>
<webroot>/usr/share/mediatomb/web</webroot>
<storage>
<sqlite3 enabled="yes">
<database-file>mediatomb.db</database-file>
</sqlite3>
<mysql enabled="no">
<host>localhost</host>
<username>mediatomb</username>
<database>mediatomb</database>
</mysql>
</storage>
<protocolInfo extend="no"/><!-- For PS3 support change to "yes" -->
<!--
Uncomment the lines below to get rid of jerky avi playback on the
DSM320 or to enable subtitles support on the DSM units
-->
<!--
<custom-http-headers>
<add header="X-User-Agent: redsonic"/>
</custom-http-headers>
<manufacturerURL>redsonic.com</manufacturerURL>
<modelNumber>105</modelNumber>
-->
<!-- Uncomment the line below if you have a Telegent TG100 -->
<!--
<upnp-string-limit>101</upnp-string-limit>
-->
<extended-runtime-options>
<ffmpegthumbnailer enabled="yes">
<thumbnail-size>128</thumbnail-size>
<seek-percentage>5</seek-percentage>
<filmstrip-overlay>yes</filmstrip-overlay>
<workaround-bugs>no</workaround-bugs>
<image-quality>8</image-quality>
</ffmpegthumbnailer>
<mark-played-items enabled="yes" suppress-cds-updates="yes">
<string mode="prepend">*</string>
<mark>
<content>video</content>
</mark>
</mark-played-items>
</extended-runtime-options>
</server>
<import hidden-files="no">
<filesystem-charset>UTF-8</filesystem-charset>
<metadata-charset>UTF-8</metadata-charset>
<autoscan use-inotify="yes">
<directory location="/media/Gurt/1_TV" mode="inotify" recursive="yes" hidden-files="no"/>
<directory location="/media/Gurt/2_Film" mode="inotify" recursive="yes" hidden-files="no"/>
<directory location="/media/Gurt/7_Downloads" mode="inotify" recursive="yes" hidden-files="no"/>
<directory location="/media/Gurt/4_Exercise" mode="inotify" recursive="yes" hidden-files="no"/>
<directory location="/media/Gurt/3_Music" mode="inotify" recursive="yes" hidden-files="no"/>
</autoscan>
<scripting script-charset="UTF-8">
<virtual-layout type="disabled"/>
</scripting>
<mappings>
<extension-mimetype ignore-unknown="no">
<map from="mp3" to="audio/mpeg"/>
<map from="ogx" to="application/ogg"/>
<map from="ogv" to="video/ogg"/>
<map from="oga" to="audio/ogg"/>
<map from="ogg" to="audio/ogg"/>
<map from="ogm" to="video/ogg"/>
<map from="asf" to="video/x-ms-asf"/>
<map from="asx" to="video/x-ms-asf"/>
<map from="wma" to="audio/x-ms-wma"/>
<map from="wax" to="audio/x-ms-wax"/>
<map from="wmv" to="video/x-ms-wmv"/>
<map from="wvx" to="video/x-ms-wvx"/>
<map from="wm" to="video/x-ms-wm"/>
<map from="wmx" to="video/x-ms-wmx"/>
<map from="m3u" to="audio/x-mpegurl"/>
<map from="pls" to="audio/x-scpls"/>
<map from="flv" to="video/x-flv"/>
<map from="mkv" to="video/x-matroska"/>
<map from="mka" to="audio/x-matroska"/>
<!-- Uncomment the line below for PS3 divx support -->
<!-- <map from="avi" to="video/divx"/> -->
<!-- Uncomment the line below for D-Link DSM / ZyXEL DMA-1000 -->
<!-- <map from="avi" to="video/avi"/> -->
</extension-mimetype>
<mimetype-upnpclass>
<map from="audio/*" to="object.item.audioItem.musicTrack"/>
<map from="video/*" to="object.item.videoItem"/>
<map from="image/*" to="object.item.imageItem"/>
<map from="application/ogg" to="object.item.audioItem.musicTrack"/>
</mimetype-upnpclass>
<mimetype-contenttype>
<treat mimetype="audio/mpeg" as="mp3"/>
<treat mimetype="application/ogg" as="ogg"/>
<treat mimetype="audio/x-flac" as="flac"/>
<treat mimetype="image/jpeg" as="jpg"/>
<treat mimetype="audio/x-mpegurl" as="playlist"/>
<treat mimetype="audio/x-scpls" as="playlist"/>
<treat mimetype="audio/x-wav" as="pcm"/>
<treat mimetype="audio/L16" as="pcm"/>
<treat mimetype="video/x-msvideo" as="avi"/>
<treat mimetype="video/mp4" as="mp4"/>
<treat mimetype="audio/mp4" as="mp4"/>
<treat mimetype="application/x-iso9660" as="dvd"/>
<treat mimetype="application/x-iso9660-image" as="dvd"/>
<treat mimetype="video/x-matroska" as="mkv"/>
<treat mimetype="audio/x-matroska" as="mka"/>
</mimetype-contenttype>
</mappings>
<online-content>
<YouTube enabled="no" refresh="28800" update-at-start="no" purge-after="604800" racy-content="exclude" format="mp4" hd="no">
<favorites user="mediatomb"/>
<standardfeed feed="most_viewed" time-range="today"/>
<playlists user="mediatomb"/>
<uploads user="mediatomb"/>
<standardfeed feed="recently_featured" time-range="today"/>
</YouTube>
</online-content>
</import>
<transcoding enabled="no">
<mimetype-profile-mappings>
<transcode mimetype="video/x-flv" using="vlcmpeg"/>
<transcode mimetype="application/ogg" using="vlcmpeg"/>
<transcode mimetype="application/ogg" using="oggflac2raw"/>
<transcode mimetype="audio/x-flac" using="oggflac2raw"/>
</mimetype-profile-mappings>
<profiles>
<profile name="oggflac2raw" enabled="no" type="external">
<mimetype>audio/L16</mimetype>
<accept-url>no</accept-url>
<first-resource>yes</first-resource>
<accept-ogg-theora>no</accept-ogg-theora>
<agent command="ogg123" arguments="-d raw -o byteorder:big -f %out %in"/>
<buffer size="1048576" chunk-size="131072" fill-size="262144"/>
</profile>
<profile name="vlcmpeg" enabled="no" type="external">
<mimetype>video/mpeg</mimetype>
<accept-url>yes</accept-url>
<first-resource>yes</first-resource>
<accept-ogg-theora>yes</accept-ogg-theora>
<agent command="vlc" arguments="-I dummy %in --sout #transcode{venc=ffmpeg,vcodec=mp2v,vb=4096,fps=25,aenc=ffmpeg,acodec=mpga,ab=192,samplerate=44100,channels=2}:standard{access=file,mux=ps,dst=%out} vlc:quit"/>
<buffer size="14400000" chunk-size="512000" fill-size="120000"/>
</profile>
</profiles>
</transcoding>
</config>