Reusing a USB Boot Drive - Format back to factory state?

You did not provide any information about which version of Windows you are using or about what sort of partitioning this USB drive is using.

If you are using Windows 7 then perhaps it cannot delete the partitions because your USB drive was GPT formatted by your Mac? If that is the case, then run DISKPART from an (elevated) command prompt. If a partition is READ ONLY or HIDDEN I don't think it can be deleted unless you force it. For example, use DELETE PARTITION OVERRIDE.

See the HELP for DISKPART for more info if you need it.

Of course, using dd from a Linux Live CD boot is also a way to clear the drive. FWIW, you don't have to write zeros to the entire USB drive. Just clearing the first MiB or so would do it. Adding count=2 to the example in hotei's answer should accomplish this.
dd if=/dev/zero of=/dev/usb_device_name_goes_here bs=1024k count=2

Unless I've screwed it up the above should write 2 blocks of 1024k (1MiB) zero bytes to the device you specify as the outfile (of=). This will wipe out the partition table whether it is GPT or MBR and then Windows can partition it as you wish.

Easiest way is to boot up a Unix/Linux live CD and then use dd to write zeroes to drive:

Insert drive into the USB port but do NOT mount it.

dd if=/dev/zero of=/dev/usb_device_name_goes_here bs=1024k

This will zap it back to it's original state. When Windows or Unix tries to use it later it will recognise that it needs to be "partitioned" and "formatted" and you can go from there.

Edited: If you're not familiar with Unix/Linux you should probably disconnect your hard drives before doing this just to be safe. Just connect the CD and the USB drive you want to format.

If you have access to a Linux box, using the dd command to copy zeroes to the device itself, not the partition, could make your disk restart from fresh.

When using the command, make sure you use the right device. If you mount your disk on the USB port, its name should be something like /dev/sdb, or /dev/sdc. The third letter is sequential and indicates the physical device as detected. Since you likely have one internal hard disk, you should not ever touch /dev/sda.

If you're paranoiac (as I am sometime), disconnect all your internal hard disks, just leaving a cdrom drive, and boot from it, using knoppix or Ubuntu Live CD. From there, connect your drive to repartition, and either use the dd utility as stated previously, or use gparted to manage the partitions on the device. If gparted does not work, this would be because it would not recognize the partition table. Doing this dd command first should clear the problem.