Do you have package coreutils or coreutils-gnu? These are different packages and dist-upgrade needs first one.
~# apt-get upgrade -s Reading package lists... Done Building dependency tree Reading state information... Done The following packages have been kept back: hildon-initscripts libcurl3 libgcc1 libsdl-mixer1.2 libstdc++6 libxau6 0 upgraded, 0 newly installed, 0 to remove and 6 not upgraded. delite:~# apt-get dist-upgrade -s Reading package lists... Done Building dependency tree Reading state information... Done Calculating upgrade... Done The following packages will be REMOVED: cell-modem-ui diffutils-gnu git grep-gnu The following NEW packages will be installed: diffmo gcc-4.6-base libkeyutils1 libkrb53 libvorbisfile3 The following packages have been kept back: hildon-initscripts libcurl3 libgcc1 libsdl-mixer1.2 libstdc++6 libxau6 WARNING: The following essential packages will be removed. This should NOT be done unless you know exactly what you are doing! grep-gnu 0 upgraded, 5 newly installed, 4 to remove and 6 not upgraded.