Tu les as comparés avant de le supprimer ?
Bon, au pire, ce sont les certificats qui déconneront ...
Pour forcer l'installation de kdelibs-data-kde3 :
sudo dpkg -i --force-all /var/cache/apt/archives/kdelibs-data-kde3_4%3a3.5.12-0ubuntu6+r1152788_all.deb
Après, pour le fait que kdelibs-data installe un fichier dans /etc/kde3, je suppose que c'est pour des raisons de compatibilité, ces fichiers étant communs à KDE3 et KDE4, mais puisqu'à la base ils étaient dans KDE3 ...
Quant à savoir si le problème viens de Trinity, de KDE4 ou des packageurs des paquets ... j'en sais rien. Lucid a une vieille version de KDE4.
Depuis Kubuntu 11.10 (KDE4.7), kdelibs-data est remplacé par kdelibs5-data, qui installe ksslcalist dans /usr/share/kde4/config, donc plus de conflit.
En revanche, je ne crois pas que le fait d'être en 32bits ou 64 bits y change quelque chose. Les paquets kdelibs-data et kdelibs-data-kde3 sont des paquets "all", donc les mêmes pour les 2 architectures.