I had a similar problem with the 1.03 patch due to having the European game client (for some reason) despite living in Canada. These steps are what fixed the problem for me (but do them at your own risk, as manually editing config files is not without risks). Assuming you're using Windows:
Make sure that Diablo is closed. Go to C:\ProgramData\Battle.net\Agent (you might have to set Windows Explorer to show hidden files).
Open "agent.db" in a text editor (like notepad).
There should be three instances of the line http://enXX.patch.battle.net:1119/patch where XX is the region that it currently thinks you're in. In my case it said enGB (for Great Britain). Change all three instances to the proper region. In my case I changed it to enUS, but from this thread, it sounds like someone in Australia who was having the same problem changed it to DL and it worked for them. I'd suggest trying DL anad seeing if that works, so the final result would be http://enDL.patch.battle.net:1119/patch
Save the file and try starting Diablo again. The patch should download if this fix was successful.