Если во время удаления пакета выдает "Failed dependencies" надо сначала удалить зависимые пакеты. В твоем случае перед удалением пакета mysql-3.23.58-16.FC2.4.legacy надо удалить зависимости perl-DBD-MySQL-2.9003-4, libdbi-dbd-mysql-0.6.5-8.1, mysql-server-3.23.58-16.FC2.4.legacy, mysql-devel-3.23.58-16.FC2.4.legacy, psa-prevztune-1.0-2.swsoft, mysql-server-3.23.58-16.FC2.4.legacy, mysql_passwd-0.7-2.swsoft
Выше былозамени на