I have postponed this for some time, then I finally stumbled upon jDownloader!
It's java-based so you will probably need java:
sudo apt-get install sun-java6-jre sun-java6-bin sun-java6-fonts
It features many useful stuff, one them is the cute interface (GTK-like), also many themes to appeal your eye. Moreover, you can use the Captcha Exchange Service with this nifty downloader. A built-in default CAPTCHA service is the jAC (java anti-captcha), which starts to automatically "learn" captchas and can make typing CAPTCHAs a breeze (Of course you have to type the first say 20-30 captchas).
Another great service is their addons, directly or downloadable through rapidshare, easily enabled and disabled through configuration (Don't forget to check "Expert mode" for more features!).
The downside is that it's sometimes buggy, still needs to be worked with. It also needs is a good language translator, since some important messages are still left in German, and... "Kein sprechenzi Deutche"!
But being limited, this downloader is the best so far, gets an overall score: 8/10 stars! :)