Problem is not really a problem, its just how apt is designed to work. If an already installed package has an update available and this new version has a new dependency, apt-get update does not automatically fetch that new dependency.

Easiest solution:

apt-get dist-upgrade