I know that my USB powered Hard Drive doesn't work, but what is the minimum power requirement that the Raspberry Pi can fulfil for devices that connect via USB?
In reality, it is more complicated than this.
I've taken two screenshots from the Device B schematic (released here):
Power in (fig A):
We can see that the 5 volt line (+5V0) is powered directly from the USB input power, through a 1.1A, 6V Polyfuse (miniSMD). I believe this means that the 5V input is current limited to 1.1A (maximum hold current, not peak).
Let's assume that you're powering the device from a regulated 5V supply capable of supplying at least 700mA.
USB Power out (fig B):
As we can see from fig B, the USB ports are current-limited by polyfuses (miniSMDC014) to 140mA (constant draw).
Some users have discovered that their polyfuses at 100mA have approx 5 Ohm resistance, causing a voltage drop of V = iR = 0.1*5 = 0.5 V. This isn't ideal, as this means the output USB voltage would be 5 - 0.5 = 4.5 V. (This may cause some devices to not function if they expect 5.0 V)
As the current draw on the USB increases (ie to 150mA), voltage drops further - 0.15*5 = 0.75 V, resulting in an output voltage of 5 - 0.75 = 4.25 V, which is below the USB spec minimum voltage of 4.40V (source). This is assuming the resistance doesn't increase with current draw, although in reality the resistance/current draw plot will look something like this:
From a Q/A with Pete Lomas:
To power higher power devices: (i.e. USB 2 devices)
You should use a powered USB hub, that can supply >= 0.5A per USB port. This means if your USB hub has 4 ports, it should use at least a 2A power supply.
If you don't want to use a USB hub with a second power supply, you can do one of the following options:
Just noting that the rev 2.0 board no longer has the USB polyfuses, just the input 1.1A polyfuse. So the issues mentioned here should no longer be present in current generation Raspberry Pi boards.