Why do I have to format external disk twice? (First time will always fail)
The first time you try to format the disk it 'fails' to unmount the volume then unmounts it and returns an error. The second time the drive is already unmounted, so the erase usually succeeds. Since I've seen this on new macs and new installations, I think it is a Disk Utility bug. 

An easy workaround is to unmount the volume you want to erase before erasing.

Using the diskutil command in terminal doesn't give the same error.