Under FDisk you need to delete any non-dos Partitions and create a new (Dos) one.
If it doesn't let you it's worth trying Linux FDisk instead, as that allows better control over the raw partition info.
If you still can't get anywhere it's probably broke :-(
EDIT: As with Amigas, once partitionned you'll need to reboot and format it!
