Here's what I found with an 8 MegaByte card (yes, 8 *Mega*Byte):
SdFatInfo showed that it was formatted as FAT12. (The fat16info sketch gave the same information. See Footnote.)
Cluster size was 4, Cluster count was 3299. Note that the cluster size is the number of 512-byte blocks within a cluster. In Windows terminology, that means that the allocation unit size is 2048. This knowledge is important for the next step.
Now, neither the Fat16 library nor the SdFat library will do anything (other than the respective info sketches) with a Fat12 card.
So...here's what I did:
I plugged the 8 MegaByte SD card into my Windows XP workstation, and I went to Control Panel->Computer Management->Disk Management
When I went to format the card, the dialog box gave me the option of "FAT" or "FAT32." I selected FAT. It did not give me the option of FAT12 or FAT16, but it did let me select the allocation unit size.
Since I already knew that an allocation unit size of 2048 would result in a FAT12 format, I selected allocation unit size of 1024. That gives more allocation units that can be expressed as a 12-bit number, so I was hopeful that it would give me a FAT16 result.
Formatting was real fast. I did the "Safely Remove Hardware" thing and plugged the SD card back into my Arduino circuit.
Now fat16info shows me that it is, indeed, a FAT16 file system with cluster size 2 and cluster count 6583.
I can write, read, do the benchmark, do the fat16ls thing, etc.
Bottom line: To make Windows format it as FAT16 instead of FAT12 you have to increase the cluster count. You accomplish this by decreasing the allocation unit size, not increasing it. Nothing that I have seen in Windows itself reports whether it is doing a FAT12 format or a FAT16 format. Run fat16info or SdFatInfo to make sure that it's not FAT12 before you try the other good stuff.
I tested the FAT12-FAT16 thing with the Fat16 library and also with the SdFat library. I always use the SdFat library since it handles SDHC cards as well (I have some 4 GigaByte and 8 GigaByte cards). Using the SdFat library, the only cards that I have had to re-format are the small ones that came as FAT12.