What is "dist-upgrade" and why does it upgrade more than "upgrade"?

From apt-get manual:

upgrade
   upgrade is used to install the newest versions of all packages
   currently installed on the system from the sources enumerated in
   /etc/apt/sources.list. Packages currently installed with new
   versions available are retrieved and upgraded; under no
   circumstances are currently installed packages removed, or packages
   not already installed retrieved and installed. New versions of
   currently installed packages that cannot be upgraded without
   changing the install status of another package will be left at
   their current version. An update must be performed first so that
   apt-get knows that new versions of packages are available.

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.

And with the newer apt tool available from 14.04 onwards:

full-upgrade
   full-upgrade performs the function of upgrade but may also remove
   installed packages if that is required in order to resolve a
   package conflict.

In your particular case, I see, for example, that linux-headers is a virtual package that is provided by both linux-headers-3.0.0-12 and linux-headers-3.0.0-13 and that sounds like the kind of package installation and removal handled by dist-upgrade, but not by upgrade.

apt-get upgrade is restricted to the case where packages are to be replaced by newer versions, but no package needs to be added or removed. A new version of Firefox, for instance, should be installable with apt-get upgrade.

However apt-get upgrade will refuse to work when there are additions or removals required by the updated versions. For example, when you have kernel linux-image-3.2.0-10-generic installed and linux-image-3.2.0-11-generic appears, the linux-image-generic package gets updated to depend on the newer version. In order to install the new kernel, you need to run apt-get dist-upgrade.

Notice how an apt-get upgrade will say that the kernel packages have been held back. That's the cue for using apt-get dist-upgrade.