I thought the error was because that particular host was having troubles, but I'm seeing it on other hosts too now. I'm did a quick change to replace my URLFetch calls with normal socket based http calls through OkHttp, and that seems to be better, though it's to soon to really tell.
I'm using Java 8, but since this is an older app it's still using the URLFetchService as that was the only way to do a request in the past. I don't really need it to be replaced, I just need it to work like it used to and not fail at random :-)