I had your exact same problem.  I eventually solved the problem by using a second Linux system that I happened to have.

One thing that may work is to install "persistent-less" LinuxCoin.  Then go into fdisk and re-partition the drive into two partitions, commit the partition table, and exit... then immediately unplug the drive.  This is risky because you're nuking the partition that the OS is using... but as soon as you commit the new partition table you don't need the OS any more.  Then you can plug the drive into  your win7 system and win7 will format only the first partition and leave the second partition alone.  Then once you get LinuxCoin up and running again you can set up the second live-rw partition to get persistence working.

This may or may not work, I don't know.  I can think of a couple of reasons why it wouldn't work.  You'll have to try it.

A second possibility may be to plug in two USB drives at the same time.  Use one to boot "persistentless" Linux.  Then, use that OS to partition the second drive that isn't being used by the OS.  This is safer than the method above and will almost certainly work, but requires two USB drives.