Comment 4 for bug 291381

(Executive summary:
Uninstall the old kernels with Synaptic.
Simply deleting the files in /boot won't satisfy the Distribution Upgrade.)

I was seeing this problem as well. My /boot is 100MB, and I had gone and freed up ~70+MB by deleting the files for my old kernels. Still the installer complained that it wanted 75.7MB free in /boot. This happened to me on both a network upgrade and trying an installation from an alternative install CD.
In my /var/log/dist-upgrade/main.log I see...

2008-10-31 10:32:19,078 DEBUG Dir /usr mounted on /
2008-10-31 10:32:19,079 DEBUG Dir /var mounted on /
2008-10-31 10:32:19,079 DEBUG Free space on /boot: 73176064
2008-10-31 10:32:19,080 DEBUG Dir /var/cache/apt/archives mounted on /
2008-10-31 10:32:19,080 DEBUG Dir /home mounted on /
2008-10-31 10:32:19,080 DEBUG fs_free contains: '{'/var': <DistUpgradeController
.FreeSpace object at 0x5503390>, '/home': <DistUpgradeController.FreeSpace objec
t at 0x5503390>, '/boot': <DistUpgradeController.FreeSpace object at 0x5503510>,
 '/usr': <DistUpgradeController.FreeSpace object at 0x5503390>, '/': <DistUpgrad
eController.FreeSpace object at 0x5503390>, '/var/cache/apt/archives': <DistUpgr
adeController.FreeSpace object at 0x5503390>}'
2008-10-31 10:32:19,178 DEBUG linux-image-2.6.24-21-generic (upgrade|installed)
added with 12582912 to boot space
2008-10-31 10:32:19,201 DEBUG linux-image-2.6.22-14-generic (upgrade|installed)
added with 12582912 to boot space
2008-10-31 10:32:19,209 DEBUG linux-image-2.6.24-19-generic (upgrade|installed)
added with 12582912 to boot space
2008-10-31 10:32:19,266 DEBUG linux-image-2.6.24-16-generic (upgrade|installed)
added with 12582912 to boot space
2008-10-31 10:32:19,309 DEBUG linux-image-2.6.27-7-generic (new-install) added w
ith 12582912 to boot space
2008-10-31 10:32:19,312 DEBUG linux-image-2.6.24-18-generic (upgrade|installed)
added with 12582912 to boot space
2008-10-31 10:32:20,269 DEBUG dir '/var/cache/apt/archives' needs '559011054.0'
of '<DistUpgradeController.FreeSpace object at 0x5503390>' (25410088960.000000)
2008-10-31 10:32:20,270 DEBUG dir '/usr' needs '665604096.0' of '<DistUpgradeCon
troller.FreeSpace object at 0x5503390>' (24851077906.000000)
2008-10-31 10:32:20,270 DEBUG dir '/usr' needs '52428800' of '<DistUpgradeContro
ller.FreeSpace object at 0x5503390>' (24185473810.000000)
2008-10-31 10:32:20,270 DEBUG dir '/boot' needs '75497472' of '<DistUpgradeContr
oller.FreeSpace object at 0x5503510>' (73176064.000000)
2008-10-31 10:32:20,271 ERROR not enough free space on /boot (missing 2321k)
2008-10-31 10:32:35,372 DEBUG openCache()
2008-10-31 10:32:35,663 DEBUG /openCache()

...hmmm, I've deleted the old kernel files from /boot, but if I interpret the aborted install log correctly it looks like the old kernels are still being used in some calculation of the space on /boot. I launched synaptic package manager and searched on "kernel". I selected my older kernels for complete removal. Upon removing them and launching the upgrade again I get past the /boot free space error and am prompted to start the upgrade.