Since yum isn't capable of downgrading the correct package, I decided to try smart.
And after a couple hours (literally) of computing transactions, it worked.
Now, there's definitely some cleanup to do, but it's pretty good. Unfortunately smart isn't available for RHEL 5 yet (I've emailed rpmforge to request it), but things are looking pretty good.
The biggest problem is that yum doesn't work. After quickly fixing the python-elementtree package, yum now says:
# yum clean all
Loading "installonlyn" plugin
Could not find any working storages.
Fortunately, here's how to fix it.
For me it was:
# rpm -Uvh sqlite-3.3.6-2.i386.rpm python-sqlite-1.1.7-1.2.1.i386.rpm
And here's the config I used for smart:
smart channel --add "Silfreed.net" type=rpm-md priority=-3 baseurl=http://www.silfreed.net/download/repo/rhel/5/i386/silfreednet -y`
smart channel --add "Dries" type=rpm-md priority=-5
baseurl=http://ftp.belnet.be/packages/dries.ulyssis.org/redhat/el5/en/i386/dries/RPMS
-y
smart channel --add "Dag" type=rpm-md priority=-5
baseurl=http://apt.sw.be/redhat/el5/en/i386/dag/ -y
smart channel --add "EPEL" type=rpm-md priority=-2
baseurl=http://download.fedora.redhat.com/pub/epel/5/i386 -y
smart channel --add "CentOS Base" type=rpm-md
baseurl=http://mirror.centos.org/centos/5/os/i386/ -y
smart channel --add "CentOS Updates" type=rpm-md
baseurl=http://mirror.centos.org/centos/5/updates/i386/ -y
smart channel --add "CentOS Addons" type=rpm-md
baseurl=http://mirror.centos.org/centos/5/addons/i386/ -y
smart channel --add "CentOS Extras" type=rpm-md
baseurl=http://mirror.centos.org/centos/5/extras/i386/ -y