yes, linux writes its boat loader to the boot record, not the partition. so when you format partitions the boot record isnt touched. there is a varity of ways of remaking the MBR, but using fdisk is fairly ok so run with that

Ive had the same problem once before. depending on the size of your hdd, you might want to consider a dual boot even if your comp is slow. but if the partition is a fat16 i dont think you would have room.

-cheers