I'm also from Melbourne and seeing the same problem. I'd been blaming my ISP but apparently that's not the case. It's extremely frustrating.

 

Update: Downloading older videos still seems to work without a problem.