So, I was repartitioning a harddrive that used to be a windows disk. I removed the ntfs partition that was spanning the whole drive and created a linux layout instead (two linux partitions and one swap). After writing the partition table the first partition on the disk failed to format. Returning to fdisk I saw that the first partition was still of type NTFS. So I changed the type once more and wrote the partition table to disk. I exited and returned and the type was stubbornly set to ntfs.
The fix was to zero the first megabyte of the partition:
dd if=/dev/zero of=/dev/sdx1 bs=1024k count=1
If you don’t understand the above don’t run it ! You risk a lot if you mistake the target partition!