Hola:
     Prueba si quieres como te acertadamente indica Mr X  con el gdisk, pero si el disco es nuevo y sin particionar no deberia darte tantos problemas con fdisk..  
Otras opciones  tambien son:
-Usar los programas especificos que tienen los fabricantes de los discos, aunque  yo solo los he usado en situaciones obligadas..
-Usar el disco de win xp para hacer las particiones con él..
           Mi duda es que si estas siguiendo correctamente los pasos y los pc,s estan en orden,  quizá el disco esté dañado o,  ya estaba particionado previamente con otro programa y antes de particionarlo tú, debas eliminar esas particiones anteriores.
Un saludo