apt-get clean sounded interesting, but it is failing with "could not open lock file /var/cache/apt/archives/lock open (13 Permission denied" followed by "E: Unable to lock the download directory".

This is after rebooting, and even "df -k" is failing. Previous reboots hadn't freed up space, and didn't work this time.