It looks like Mojang deployed a new rate limiting rule for downloading skins. Earlier this was one request per minute per UUID. Now it seems like it's 10 per minute in total. I'm working on it ASAP to provide an alternative solution.

This also applies to skulls.

After further testing it seems to be 10 allowed skin downloads per 30 seconds.