Ubuntu Server message says packages can be updated, but apt-get does not update any [duplicate]

Possible Duplicate:
updates in amazon-ec2 ubuntu 10.04 server

When I log into an Ubuntu 10.04.2 LTS server, I see the message:

42 packages can be updated.
18 updates are security updates.

But when I try to update this, nothing gets upgraded as would be expected:

$ sudo apt-get update
....snip....
Reading package lists... Done
$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages have been kept back:
  linux-generic-pae linux-headers-generic-pae linux-image-generic-pae
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.

Any ideas why either nothing was updated, or why the count of 3 (from apt-get) is different than 42? What software says 42 if not apt?

(Other details: This is the server edition, no GUI; I haven't touched the apt configuration files; when I installed the software, I declined to allow automatic updates)

Solution 1:

In order to install packages kept back you have to run:

sudo apt-get update && sudo apt-get dist-upgrade

Trying to run just sudo apt-get update && sudo apt-get upgrade wont install packages kept back because apt-get upgrade by default does not try to install new packages (such as new kernel versions); from the man page: under no circumstances are currently installed packages removed, or packages not already installed retrieved and installed.

However apt-get dist-upgrade allows you to install new packages when needed (ie, a new kernel version); From the man page:

  dist-upgrade
       dist-upgrade in addition to performing the function of upgrade, also intelligently handles changing dependencies with new
       versions of packages; apt-get has a "smart" conflict resolution system, and it will attempt to upgrade the most important
       packages at the expense of less important ones if necessary. So, dist-upgrade command may remove some packages. The
       /etc/apt/sources.list file contains a list of locations from which to retrieve desired package files. See also
       apt_preferences(5) for a mechanism for overriding the general settings for individual packages.

Solution 2:

This message is coming from the MOTD (message of the day) system. Details of how to fix the incongruity between this message and the package manager were covered recently in this answer.