Hm. I had the exact same issue with a different hosting provider and resolved it by moving to digital ocean.
What geographic location did you chose for the droplet?