After a lot of searching, I found the solution if anyone else has the same problem.
Just download this from HP:
Drive Boot Utility
It will zap everything off of a removable device and create a new FAT partition. This has even worked for removing the U3 software on the Sandisk USB drives.