I had the same problem. I just upgraded them all to unstable (Sid). That worked.
Of course, you run unstable/Sid at your own risk.
At this point, we can have the discussion that Unstable is more secure than Testing (Sarge), since neither gets "official" Security fixes, but Testing has to wait at least 10 days for fixes to percolate in from Unstable.
You can always "downgrade" back to Sarge once this packaging problem gets fixed.
There are two "Grave" bug reports against gcc and gcc-base for these problems - 268476