I also had pdoblems creating a fat16 partition (in Linux). The problem was I was creating FAT32 partitions all the time (assuming partition type has something to do with it, but GNU utilities could not care less about the partition type). I realised I need to use -F 16 (from man mkfs) as per KdL's post.
Try fsck -v, it should tell you which FAT you are using (but only with -v).
I'm using Zemmix Neo, which will boot to BASIC. but obviously a wrongly created fat partition didn't work. After getting a FAT16 partition, works like charm :-)
