Analysis from the resolver:

# apt-get -oDebug::pkgProblemResolver=true dist-upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Calculating upgrade... Starting
Starting 2
Investigating (0) console-setup [ amd64 ] < 1.57ubuntu20 -> 1.57ubuntu25 > ( utils )
Broken console-setup:amd64 Conflicts on console-terminus [ amd64 ] < 4.30-2 > ( fonts )
  Considering console-terminus:amd64 -1 as a solution to console-setup:amd64 11
  Added console-terminus:amd64 to the remove list
  Fixing console-setup:amd64 via remove of console-terminus:amd64
Investigating (0) gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs )
Broken gcc-4.4-base:amd64 Breaks on gcj-4.4-base [ amd64 ] < 4.4.5-15ubuntu3 -> 4.4.6-2ubuntu2 > ( libs ) (< 4.6.1-4ubuntu2~)
  Considering gcj-4.4-base:amd64 8 as a solution to gcc-4.4-base:amd64 3
  Holding Back gcc-4.4-base:amd64 rather than change gcj-4.4-base:amd64
Investigating (0) cpp-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( interpreters )
Broken cpp-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to cpp-4.4:amd64 1
  Holding Back cpp-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (0) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (1) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
 Try to Re-Instate (1) gcc-4.4-base:amd64
 Try to Re-Instate (1) cpp-4.4:amd64
Investigating (1) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (2) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (2) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (3) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (3) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (4) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (4) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (5) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (5) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (6) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (6) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (7) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (7) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (8) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (8) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Investigating (9) libgcc1 [ amd64 ] < 1:4.5.2-8ubuntu4 -> 1:4.6.1-9ubuntu3 > ( libs )
Broken libgcc1:amd64 Breaks on gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel ) (< 4.4.6-4)
  Considering gcc-4.4:amd64 0 as a solution to libgcc1:amd64 422
  Upgrading gcc-4.4:amd64 due to Breaks field in libgcc1:amd64
Investigating (9) gcc-4.4 [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( devel )
Broken gcc-4.4:amd64 Depends on gcc-4.4-base [ amd64 ] < 4.4.5-15ubuntu1 -> 4.4.6-11ubuntu1 > ( libs ) (= 4.4.6-11ubuntu1)
  Considering gcc-4.4-base:amd64 3 as a solution to gcc-4.4:amd64 0
  Holding Back gcc-4.4:amd64 rather than change gcc-4.4-base:amd64
Done
Failed
The following packages have unmet dependencies:
 libc6-dev : Breaks: gcc-4.4 (< 4.4.6-3ubuntu1) but 4.4.5-15ubuntu1 is to be installed
 libgcc1 : Breaks: gcc-4.4 (< 4.4.6-4) but 4.4.5-15ubuntu1 is to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.
(natty)root@borges:~# apt-get dist-upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Calculating upgrade... Failed
The following packages have unmet dependencies:
 libc6-dev : Breaks: gcc-4.4 (< 4.4.6-3ubuntu1) but 4.4.5-15ubuntu1 is to be installed
 libgcc1 : Breaks: gcc-4.4 (< 4.4.6-4) but 4.4.5-15ubuntu1 is to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.

The libc6-dev Breaks: is clear enough because the old compiler won't find libc.so or some of the headers; but why do we have a breaks: from libgcc1, the runtime lib?  Matthias?