You say you tried APT, are you talking about apt-get, which, if you get synaptic (the gui for apt-get) takes care of these things. If you are still having trouble you could always go to
www.freshrpms.net or
www.rpmfind.net and find the exact file you need and install it with the --force command.
PS: please click on "user cp" at the top of the page once you are logged in and edit profile to include the distro(s) you are using, it will make it easier for others to give more exact answers.
rberry88