Throwing this piece of information out to the web-spiders of the world. Perhaps someone else can benefit from my experience.
I'm upgrading my Fedora Linux systems, and I noticed that there was one package that was causing problems - I had a copy of Avahi from FC6 which hadn't got properly upgraded by the more-or-less automated processes. Or, doing more investigation, there was a (nearly) up-to-date version as well as the old version, both installed. The yum system should take care of that, and so it's not so surprising that once it's in the failure case, it's tricky to get it to remove the old copy.
I tried doing the obvious thing of yum remove avahi-blah-blah-fc6, which "succeeded", but the package was still installed. In fact, I could keep on issuing that remove command, which kept on "succeeding".
I tried rebuilding the RPM database, which also succeeded, but didn't change anything - the fc6 version of avahi was still around.
I tried rpm -e avahi-blah-blah-fc6, which complained about scriptlets failing (though no indication what a scriptlet is, or what the failure was). I then tried rpm -e --noscripts avahi-blah-blah-fc6 and that seemed to do the trick - the RPM database now no longer has a record of the old avahi, and I'm able to do a yum update just fine.