I had the same problem with error 404 when downloading YouTube videos and I solved it.

After frustrating, cursing, losing a few hairs and having a few more turn gray, I found the problem.

When you copy a URL from a YouTube video in Firefox (or presumably another browser) you get something like this:

http://www.youtube.com/watch?feature=player_detailpage&v=zLHc8NR_v-8

you want to remove this portion of the string: feature=player_detailpage&v=

The above string is for the browser, or for flash player, but is not a part of the video address string.

YOU WANT THIS: http://www.youtube.com/watch?v=zLHc8NR_v-8#t=136s

When I called download with this string (with "feature_player" removed) it worked like a charm.