Just came home and tried it again making no changes from earlier and guess what? The bloody thing finally worked. Go figure....
I'm quite sure the problem was related to DNS.
Most likely, Mediafire servers changed IPs and this info need to be propagated along the DNS servers all over the world, before you can have a chance to have the serverxxx.mediafire.com name translated into an IP address.
Every ISP mantains his own DNS servers, that are configured differently to update themselves like every hour, every 2 hours, every 8 hours, every day, every 2 days, etc. This means, depending on your ISP update frequency, you can experience a delay from the moment the remote server changes its IP number, to the moment you'll be able to reference it by name.
So, your issue was that you simply had to wait that time, which might have been slower than other's.
That's why I suggested using Open DNS, because they are usually faster in updates and more accurate than any DNS provided by standard ISPs. I always use Open DNS myself, because my ISP DNS are slow and sometimes have an higher ping time, which results in overal slower surfing speed.