diff -up yum-3.4.3/yum/depsolve.py.old yum-3.4.3/yum/depsolve.py
--- yum-3.4.3/yum/depsolve.py.old	2013-04-04 18:21:22.477786494 +0200
+++ yum-3.4.3/yum/depsolve.py	2013-04-04 18:22:48.742547795 +0200
@@ -918,6 +918,9 @@ class Depsolve(object):
                                 self._last_req = None
                                 self.pkgSack.delPackage(otxmbr.po)
                                 self.up.delPackage(otxmbr.pkgtup)
+                                # Update the cache and recheck file requires
+                                (self.installedFileRequires or {}).pop(otxmbr.pkgtup, None)
+                                CheckRemoves = True
 
                 if CheckDeps:
                     if self.dsCallback: self.dsCallback.restartLoop()
@@ -1177,10 +1180,10 @@ class Depsolve(object):
 
         # get file requirements from new packages
         for txmbr in self._tsInfo.getMembersWithState(output_states=TS_INSTALL_STATES):
+            files = []
             for name, flag, evr in txmbr.po.requires:
                 if name.startswith('/'):
-                    pt = txmbr.po.pkgtup
-                    self.installedFileRequires.setdefault(pt, []).append(name)
+                    files.append(name)
                     # check if file requires was already unresolved in update
                     if name in self.installedUnresolvedFileRequires:
                         already_broken = False
@@ -1194,6 +1197,7 @@ class Depsolve(object):
                         nfileRequires.add(name)
                     fileRequires.add(name)
                     reverselookup.setdefault(name, []).append(txmbr.po.pkgtup)
+            self.installedFileRequires[txmbr.po.pkgtup] = files
 
         todel = []
         for fname in self.installedFileProviders: