Being cross-platform and Java, Jdownloader is ugly as hell, and the interface is clunky, but at least for me it's worked consistently and stably (though I'm not using any premium services, just the free stuff).
I am, however, using the cross-platform version; the interface is, from the look of it, intended to blend in with Windows Vista/7, but it works just fine on the Mac. I had started out with the Mac-specific release, which worked at first but then started crashing on me at some point. Since the non-Mac UI version ran fine, I never really bothered to figure out what was the problem. Have you tried the "general" version to see if it works better for you?
That said, Speed Download, if it works, is an awesome app--much more attractive and smooth-feeling. Never tried it on Megaupload, though, but sounds like it works.