I am not sure what the problem with your floppies is, but perhaps you can try zeroing the disk first:
Code:
# dd if=/dev/zero of=/dev/fd0 bs=1024 count=1440
Also, make sure that /dev/fd0 is a link to /dev/fd0H1440, or just use /dev/fd0H1440 as an argument to fdformat...