I had a similar problem with another site that suddenly didn't like Aussie IPs, possibly because they had reached their maximum bandwidth, as they did say in their help section they might temporarily disable access to some countries if they are close to their maximum bandwidth usage. Suddenly, it started working again (after a couple of weeks or so).
Your problem is different though, as you are trying to access eBay Australia from Australia, so the solution above might work.
