Are you using multiarch support? That will definitely cause erroneous reporting of a package as "newer than archive" by apt-show-versions; see the bug I just opened:
https://bugs.launchpad.net/ubuntu/+source/apt-show-versions/+bug/1125210 -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/312138 Title: Packages reported as newer than archive when they're not To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/apt-show-versions/+bug/312138/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs