It does eventually work, but it is very very slow

Ask support if they've moved you over to their Autonomous Database infrastructure at some point recently. That might not be your issue, but if support says yes, I'd bet you that's the problem.