GitLab.com times out on Linux

Question

I'm currently using Linux Mint 17 on my laptop and I'm almost unable to work with GitLab. The issue is pretty weird:

• GitLab.com times out every time I want to save my profile info
• GitLab.com times out every time I want to add a SSH key to my account
• GitLab.com times out when I try to ssh-keyscan it
• GitLab.com sometimes (but frequently) hangs up ("The remote hung up unexpectedly") when pushing or cloning.

The current way of dealing with the last problem is not convenient at all: I push my commits to BitBucket, then I take another laptop (with Windows), pull from BitBucket and then push to GitLab. Thing is, once the "remote hungs up" error appears, it doesn't go, no matter what I do on my primary laptop. And also, I prefer pushing via SSH, but I'm not able to.

I've got LAMP stack installed and running on my primary laptop, so I thought this might be a weird port issue or something. But when I connected to Internet via my iPhone's 3G, everything worked absolutely fine. At this point, I almost dialed my Internet provider support, but I remembered that everything works fine on both secondary laptop and on the Windows PC (when running Windows). Also, I do have Linux (Ubuntu) on both PC and secondary laptop and the same issue is there. The only time everything worked on Linux was lubuntu on Virtual Box (under Windows) on my PC.

Everything works fine with other websites (GitHub, BitBucket).

Also, my /etc/hosts file is fine, and I do not have any firewall software running (I did check).

tl;dr:

• GitLab.com randomly (but consistently) times out when using Linux and my home Internet
• Everything's fine when using Linux and my iPhone's 3G Internet
• Everything's fine when using Windows with my home Internet (did not try my iPhone 3G with Windows, as I don't see a reason to)

So the question is, what am I doing wrong on Linux?