You can skip to the "good news" in the last para if you want, but I recommend you read all of this.
Milliways comment about the HFS implementation is worth consideration. Lack of journalling on a filesystem intended for it means recovery tools for that fs type will probably not work -- risky business on a backup system. This is a result of Apple's monopolization strategies (Apple forcibly discourages their customers from using anything that isn't purchased from them).
WRT USB hard drives in general, any normal drive should work. By "normal", I mean drives that do not contain additional hardware and software as layer between the storage and the OS. Usually things like this are easily recognizable because of the features of that abstraction layer, and the fact that they require further software on the host system.
The Verbatim 53070 may or may not fall into this category as it "includes Nero BackItUp & Burn software". If that is simply software intended to run on a (Windows or Mac) host to manage the drive, it's fine. I would guess that is the case, because it is the simplest and least expensive way to do such a thing. Of course, you won't be able to use Nero on the pi.
If you've already mounted and accessed the drive from the rpi, then it is obviously OK. The issue with "failed verification" may be an issue with Time Machine (in that HFS wikipedia link above, it's implied Time Machine requires journaling; glancing through your blog link I'm not sure if this attempts to force journaling, which the wiki bit calls "unwise" == you're probably on thin ice).
It may also be that the drive is having trouble when powered directly from the pi. The general wisdom with USB drives and the pi is that they should be run from a powered hub.1 I have a 500 GB drive that I leave connected this way, and I've never had any problems with it. It's invariably mounted at boot and remains accessible 24/7 until I shut it down. I'm using the native ext4 format, however.
But -- good news. It looks like someone else has used Time Machine + netatalk with the pi but not HFS. If you have a choice, your best bets are either #1) ext4, or #2) vfat.
1 The pi's own USB ports have sub-standard amperage. If you get a cheap 3-5 amp hub (~$20) that doesn't regulate power to any particular port, you can easily run the pi and whatever else from it (i.e., just one plug).