Running apt-mark while an apt-get update was running concurrently, I got this: E: Problem renaming the file /var/cache/apt/pkgcache.bin.uuCnyh to /var/cache/apt/pkgcache.bin - rename (2: No such file or directory) W: You may want to run apt-get update to correct these problems Looks to me like either or both don't acquire a necessary lock.