yum fails in FIPS mode

I guess my Google-fu wasn't up to this one!

I have a system running CentOS 5.9 32-bit running in FIPS mode that I
would like to update. Unfortunately, it fails when attempting to run
"yum update". I've disabled all the repositories except for base and
updates and still get the same issue, an error carping about an
algorithm forbidden by FIPS. Here's what I see:

My searches seem to indicate that FIPS doesn't like MD5, which I thought
was pretty much essential to verifying the packages, but I saw no
documented work-arounds.

I've done a "yum clean all" (at least THAT works!) and it had no effect.
I get the same error on "yum repolist", just in case you were
wondering. Grasping at other straws, I checked the system time, which
is correct (using NTP anyway).

Anybody got any ideas about how to work around this? I would really
rather NOT reboot in non-FIPS mode to update the system, then reboot in
FIPS mode, but if that's the only solution that's what I'll do.