How do I erase and reformat an Apple Time Capsule?

In a curious twist of fate, this question came in just as I too was seeing the same problem, having recently upgraded the hard drive in my MacBook Pro to a huge 500GB device. My Time Capsule is also a 500GB drive (yeah, it's too small! That's a separate issue) and out of nowhere Time Machine stopped backing up and kept complaining that it needed a bigger space for its incremental than I had available.

Apparently while it deletes older backups to keep things in rotation, if you have big enough blocks, it can get into a situation where it's "stuck" and can't succeed at backing up the current increment. Not so good, and it's also not so good that Apple just leaves us hanging out to dry with no user-friendly path to solve the problem. For example, if it prompted me with "Backup device has insufficient space for normal operation. If you delete all of your hourly incremental backups for this system, however, I can proceed. Would you like to do that?"

Instead we need to do it ourselves. And here's how you do that...

You need to start with Applications --> Utilities --> Airport Utility. It should launch and immediately find your Time Capsule:

As you can see, mine is called "Time Tunnel" (a nod to a cheesy old TV show, if you must know). Click on "Manual Setup" on the bottom and you'll find that there's a ton you can configure from here:

That gives you a summary of the device. What you want to do is click on "Disks" on the top bar. Now you'll see what's going on with your disk:

As usual, you don't get access to the full size of the drive. In this case, my 500GB Time Capsule only gives me 465.8GB of actual usable space. I'm ready to proceed with the digital guillotine so I click on "Erase..." to proceed.

It asks me if I really want to do this, really want to delete all of my old backup data. I do, but I don't want to rename the device (this is the internal name: notice that "Time Tunnel" shows up on other screenshots).

I can use the quick erase if I'm going to reuse it, but if you're selling it or are otherwise concerned about the recoverability of backup data, there are some other erase options you can pick:

I suggest "Quick Erase" as the others are pretty darn slow, like overnight slow, and if you don't need to worry about it, well, why spend the time?

Once you're ready, click on "Erase..." again and you'll have yet another chance to change your mind:

Since I didn't disconnect myself, the device thinks I'm still connected to it, so I now see:

No worries, that's what I want to have happen. Click "OK".

Meanwhile, back in the Airport Utility window, you should see a progress bar:

Once that erase process is done, it'll restart the device and when you go back to "Disks" in Airport Utility, you should now see that all of the disk space is available:

Start new backups - but as with all first-time backups, connect via Ethernet for best performance, not wifi!! - and after a few hours you should be good to go.

Hope that helps. Next up for me? How to upgrade the drive inside my Time Machine...