Per me, sia su Dialup, che su Adsl, Down Them All è sempre risultato molto farraginoso e propenso a causare casini.
Sostituiscilo con l'estensione FlashGot affiancata a un buon download manager, quale può essere Free Download Manager.
Per caso, comunque, i download che ti davano un 404 erano su Rapidshare o su un altro servizio di file hosting?
Se si, faresti meglio a leggere moooolto attentamente il loro TOS...