El NON-DOS quiere decir que el disco no tiene ningún formato (esta virgen) ni siquiera el más básico el FAT de MS-DOS (de ahí NON-DOS)
Para formatear no se usa Fdisk aunque en un disco virgen es necesario crear al menos una partición con Fdisk porque si no hay partición alguna en el disco el Format que es el que si formatea de verdad no podrá formatear.
Fdisk no formatea solo crea las particiones y las toca o cambia el formato si no tuviesen formato las dejaría en NON-DOS.
En cuanto a Format el sistema en que formateara depende de la versión que uses si usas el de Windows XP podrás formatear en el sistema que quieras, si usas uno de MS-DOS solo te dejara formatear en FAT o FAT32 de todas formas aunque lo dejases en FAT o FAT32 luego seria fácil en Windows pasarlo a NTFS y a los datos no les pasaría nada.
Más información en:
http://support.microsoft.com/?kbid=255867http://support.microsoft.com/?kbid=313348