One thing... sometimes when a drive has had Linux on it, it's hard to blow away the MBR (master boot record). So although you might have blown away all the partitions from the Linux system, it might STILL boot thinking it's a Linux system. It will eventually fail because the partitions are wiped.. but the MBR remains from the Linux build.
If using fdisk, I believe you can use the "fdisk /mbr" command to wipe the master boot record clean.
Personally I like to low-level format the drives after they've had linux just to give them that sparkling clean effect
Low level formatting will take the drive back to the way it was when you got it from the manufacturer (filled with zero's). You can usually find drive utilities at the manufacturer's site, and these most always include low-level formatting tools.
Good luck!