Ssh – Gitlab – “Server refused public-key signature despite accepting key” on a valid key

I need some help with keys.

On my windows 7 machine I have created a pair of keys using Puttygen in order to connect to a private gitlab site.

In the gitlab I've added my public key to my profile.
I've connected to the server using Putty in order the cache the server fingerprint, and added GIT_SSH env variable.

On my project folder I've init the git repo, commited the changes, loaded my private key using Pageant and pushed to the server.
Everything worked as exepected – I was able to push the changes.

My problem – I wanted to use another Windows 7 machine to work on my project, I've tried using the same steps, but every time when I try to push i get:

"Server refused public-key signature despite accepting key!"

What am I doing wrong, what should I check?

Thanks for the help

Update:

I've looked at etc/var/auth.log on my server –
When I try to connect with the "refused machine", I see those lines:

localhost sshd[6979]: error: hash mismatch
localhost sshd[6979]: error: Received disconnect from *IP-of-router*: 14: No supported authentication methods available [preauth]

What or where can I get more information about this error?

Update 2:

The refused machine is connected to an ISP that uses web filtering. The ISP uses www.netspark.com, my guess is that it is related to the problem and my private key being changed or something..