The osso-software-version-rx44 package exists twice: once in your device and once in the "Nokia System Software Updates" repository. These two instances of the package have the same version, but different dependencies (stupid, I know, see below). The osso-software-version-rx44 in the repository additionally depends on the three packages that you list in the subject. Apt-get uses the information from the repository, which results in the error message you see. Running apt-get -f install will fix it. The Application manager is not affected by this, it simply ignores the problem and carries on. After the first OS update, the problem goes away. It's a bug of course that the two instances of osso-software-version-rx44 are not identical. The additional dependencies in the repository instance are used to (as you might have guessed to control flashing of the kernel and initfs during a OS update. The osso-software-version-rx44 instance in the flash image does not need them, and I didn't see the problem with this because I wasn't thinking. (I don't reflash my devices anymore, so I didn't run into this problem myself...) Yep, it's a bit embarassing, but should have no bad consequences other than having to run "apt-get -f install" once (or disabling the "Nokia System Software Updates" repository) before you can use apt-get on the command line.