Q: External Disk Drive failed

It appears that the file system on the external drive is messed up.

1) You could try a more powerful filesystem recovery tool.

Perhaps Disk Warrior has the best reputation for this:

http://www.alsoft.com/DiskWarrior/

2) you could reformat the drive with disk utility

How old is the drive?  You may want to think about replacing the hd in the external drive enclosure.  this is usually a fairly simple process.  Take apart the drive encloser to figure out what type of drive connection is used.

In the future, if Disk Utility cannot verify a drive, and gives errors, you can use an OS X utility from Terminal to attempt to repair the drive issues. If it works, you would not have to wipe your time machine drive.

1. In System Preferences : Time Machine panel, switch Time Machine off
2. Launch Terminal from Launchpad : Other
3. At the Terminal prompt:
   1. df -hl
      1. Lists your drives. You want the drive (e.g. /dev/disk2s2) associated with your mounted Time Machine volume
   2. sudo fsck_hfs -fy /dev/rdisk2s2
      1. You are performing a file system consistency check with forced (-f) repairs to your mounted (raw) Time Machine volume
      2. If it finishes normally, hooray. Otherwise, you drive may be beyond repair and recovery.
4. Provided that step 3.2.1 ended well, then verify your Time Machine disk once more in Disk Utility.
5. System Preferences : Time Machine : On

The fsck command is something that you would only run if Disk Utility could not recover the drive. As is pointed out, there is Disk Warrior v5 for El Capitan, and it should be run in Scavenge (hold down the option key when clicking Rebuild) mode. It has also become expensive, but if that can recover vital information from a damaged drive, it may be well worth it.

Disk Warrior is an expensive and specialized application whose only use is to try to recover data from a damaged volume that Disk Utility can't repair, and for which there are no backups.

If you're in that position, then instead of spending about $100 on software that you should never need again, make a "Genius" appointment at an Apple Store, where the program is available for the "Geniuses" to use on customers' machines at no charge.

The only reason to buy your own copy is that you can't get to an Apple Store, or (like Apple) you provide help-desk services to other Mac users who don't back up their data. Otherwise, Disk Warrior is a waste of money. What it does—recreating a volume directory—can be done better and faster for free by erasing the volume and restoring from a backup. That's assuming you have a working backup, of course. Not having one is a mistake you shouldn't make more than once.

The kind of directory corruption that you might need Disk Warrior to recover from can, for all practical purposes, only happen because of a hardware malfunction. It is not caused by forced shutdowns or system crashes. Any drive that malfunctions in that way should preferably be replaced at once. Even if you choose to take the risk of continuing to use the drive after the first such incident, after any repetition the drive should be wiped and recycled, not restored. Occasionally the fault might be in another internal component, or in an external drive enclosure, rather than in the drive mechanism itself.

There may still be some people who believe that rebuilding a volume directory improves performance. There has never been any evidence, as far as I know, to support that belief, and the last time I checked, the developer of Disk Warrior was no longer making such a claim on its website. Whenever I've asked DW advocates to substantiate their belief in its value, the response has always been along the lines of, "Because I say so," or "Because X says so." But every time I check, X either never made the statement, or else he has no data to support it. Nevertheless, if you have reasons of your own to believe that rebuilding a directory is a useful maintenance step—rather than pointless busywork—you can do it faster and more safely by erasing the volume and restoring from a backup. No third-party software is needed for that.

Disk Warrior is not a maintenance tool; it's a recovery tool. If you have adequate backups—which means multiple backups—you’ll never need a recovery tool, and therefore Disk Warrior is useless to you. If you don't back up, you'll eventually lose all your data, and Disk Warrior won't be able to save you. Don't waste money on it or anything like it. Spend the money on backup drives instead.

I kinda assumed that disk utility was invoking fsck_hfs to do the disk repair.

R

I  believe that you are correct. Apple used to mention fsck_hfs in single-user boot mode as an alternative approach when Disk Utility choked. It appears that they are no longer giving this advice with Disk Utility articles for Yosemite and El Capitan.

Hardware, schmardware.

This reliably happens every time I restart my iMac.

Disk Warrior is always able to rebuild the directory.

There's something fundamentally wrong with the shutdown or restart process.