Thanks very much. Yes, that explains the problem I was having. The little 256MB cards just don't support the erase function. But I confirmed that Erase works fine for my 1GB and larger cards.
I want to emphasize how much better erasing cards is than overwriting them. Overwriting leaves all the sectors as containing valid data, which must give the wear leveling algorithm fits, if the SD card uses wear leveling. And it takes forever. Erasing is very fast, and leaves all sectors as, uh, erased. And the much-touted SD Association's formatter running on your computer can't erase. So your Arduino is actually a much more capable option when you need to wipe a card.