Würde es nicht reichen wenn du einfach den MBR + die Partitionstabelle mit Nullen überschreibst und anschließend wieder eine anlegst?
Also falls der Stick /dev/sdb ist:
# dd if=/dev/zero of=/dev/sdb count=512 bs=1
# fdisk /dev/sdb
o
w
Dannach sollte man wieder normal Partitionen erstellen können. Obwohl ich nicht verstehe warum es jetzt nicht geht.