In Disk Utility, are you making sure to format the drive itself and not the partitions? In Disk Utility, it should show up as three names. The highest up is the drive and the two indented ones are the partitions. Select the drive and erase, then set up the partitions. I imagine you did that already but I'm just checking.