I haven't tried to use the gparted live cd. I know that the System Rescue CD has a bunch of utilities including gparted. This Linux live CD has been very useful to me.
Of course you really don't need to do that if you already have Linux running. You could just plug the USB disk in and use mkfs to write over the existing file system. If the USB disk shows up as /dev/sda there is already a Microsoft file system on it. That partition is called /dev/sda1. The following command would overwrite the existing file system with the ext3 file system.
mkfs -t ext3 /dev/sda1
If you want to do it right you could take the extra step to make the disk partition table show that the partition is a Linux partition. To do this you use cfdisk to change the type of partition from FAT32 to Linux.
You just select [Type] and then enter the number 83. Then you select [Write]. Then [Quit]