I've done this so many times now, and each time I've needed to google it to remind me how, so I'm putting it here for safe-keeping and reference.
The first TonidoPlug (the white one) comes with a custom Ubuntu 9.04 Jaunty image. Unfortunately that's no longer supported by Canonical, so we need to change our repos to allow us to run an apt-get update.
First though, we need to fix apt by running
mkdir -p /var/cache/apt/archives/partial
Then we change the repos by editing /etc/apt/sources.list and change the one-liner to
deb http://old-releases.ubuntu.com/ubuntu/ jaunty main restricted universe multiverse
Be ready to use nano here because you won't be able to install vim yet :)
Then you can run apt-get update and whatnot as normal.