It's not a hard-drive problem, I don't think... I think it's a FAT-16 problem. I'm not sure you'll get around it.
Question tho... if you're using linux, why in the hell are you formatting with FAT?? Shouldn't you be using EXT or EXT2?? Maybe I read you wrong tho.