dpkg indicates disk full when there is plenty of space!

Updating linux-headers-2.6.32-24-server fails with a disk full error even though there is plenty of space on all partitions:

I have booted from CDROM into recovery mode and fsck.ext4 on all partitions, root complained it was inconsistent the first time but fsck seemed to have fixed the partition

Here is the output from apt (naturally as root):
apt-get -f install
Reading package lists... Done
Building dependency tree
Reading state information... Done
Correcting dependencies... Done
The following packages were automatically installed and are no longer required:
  linux-headers-2.6.32-24-server linux-headers-2.6.32-24
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
  linux-headers-2.6.32-25 linux-headers-2.6.32-25-server
The following NEW packages will be installed:
  linux-headers-2.6.32-25 linux-headers-2.6.32-25-server
0 upgraded, 2 newly installed, 0 to remove and 1 not upgraded.
1 not fully installed or removed.
Need to get 0B/10.7MB of archives.
After this operation, 85.5MB of additional disk space will be used.
Do you want to continue [Y/n]? y
(Reading database ... 72876 files and directories currently installed.)
Unpacking linux-headers-2.6.32-25 (from .../linux-headers-2.6.32-25_2.6.32-25.44_all.deb) ...
dpkg: error processing /var/cache/apt/archives/linux-headers-2.6.32-25_2.6.32-25.44_all.deb (--unpack):
 unable to create `/usr/src/linux-headers-2.6.32-25/arch/sparc/include/asm/page_64.h.dpkg-new' (while processing `./usr/src/linux-headers-2.6.32-25/arch/sparc/include/asm/page_64.h'): No space left on device
No apport report written because the error message indicates a disk full error
                                                                              dpkg-deb: subprocess paste killed by signal (Broken pipe)
Unpacking linux-headers-2.6.32-25-server (from .../linux-headers-2.6.32-25-server_2.6.32-25.44_amd64.deb) ...
dpkg: error processing /var/cache/apt/archives/linux-headers-2.6.32-25-server_2.6.32-25.44_amd64.deb (--unpack):
 error creating symbolic link `./usr/src/linux-headers-2.6.32-25-server/include/linux/termios.h': No space left on device
No apport report written because the error message indicates a disk full error
                                                                              Errors were encountered while processing:
 /var/cache/apt/archives/linux-headers-2.6.32-25_2.6.32-25.44_all.deb
 /var/cache/apt/archives/linux-headers-2.6.32-25-server_2.6.32-25.44_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

df -k
Filesystem 1K-blocks Used Available Use% Mounted on
/dev/md1 974588192 300091936 625760672 33% /
none 508476 256 508220 1% /dev
none 511172 0 511172 0% /dev/shm
none 511172 384 510788 1% /var/run
none 511172 4 511168 1% /var/lock
none 511172 0 511172 0% /lib/init/rw
/dev/sdd1 961385948 789687000 122863360 87% /backup
/dev/md0 93143 29901 58433 34% /boot
/dev/sdc1 20650996 451716 19150240 3% /var/cache
/dev/sdc2 8262068 53188 7789184 1% /cache/squid3
/dev/sdc3 1857948 204260 1559308 12% /cache/apt-proxy

All filesystems are ext4

ls -l $(which python)
lrwxrwxrwx 1 root root 9 2010-08-28 21:24 /usr/bin/python -> python2.6

cat /proc/mdstat
Personalities : [raid1] [linear] [multipath] [raid0] [raid6] [raid5] [raid4] [raid10]
md1 : active raid1 sdb3[0] sda3[1]
      974711744 blocks [2/2] [UU]

md0 : active raid1 sdb1[0] sda1[1]
      96192 blocks [2/2] [UU]

unused devices: <none>