This thread has turned into a discussion about startups in Australia in general and let me add some perspective as an Australian who now lives in the US (NYC).
Firstly, a disclaimer: I'm from Western Australia, specifically Perth. WA is different to most of the rest of the country (except maybe Queensland) in that it awash in the biggest resources boom probably ever. Iron ore and oil and gas primarily but others too (aluminium, nickel, etc). China is of course the largest buyer.
In many ways Perth, the capital of WA and a city of some 1.5 million, is a boom town and really two cities: the haves and the have nots.
The haves are in the resources game, directly or indirectly. The biggest indirect benefactor is construction. There is some $50B+ in infrastructure projects in the pipeline and prices paid for construction are just astronomical. This was worse in the housing boom (up to 2008) but is still bad.
My brother-in-law who manages construction projects (apartment buildings and so forth) says that to build a two storey brick-and-tile house is about $2,000+/m2 (roughly $200/sq ft). Single storey is still probably $1500. Apartments in West Perth (close to the business district but not much else going on) sell for over $10,000/m2).
The have nots are everyone else including software engineers.
Post-housing bubble and because of the high cost of entry to the market (you will not find a house in Perth cheaper than $250,000 period and I'm including rundown houses built 50+ years ago) and tighter lending practices by the banks (anecdotally, the wholesale cost of lending pre-bubble bursting was 20 basis points about the RBA rate, now 100+) rents are going through the roof.
A one bedroom apartment I rented in 2005 for $300/week is now $600+. There are far more extreme examples than this.
On top of this the cost of living is ridiculous. Food, utilities, you name it.
Basically if you aren't in the resources/construction game, you have experienced a drop in your real standard of living over the last 10 years. Commercial property is expensive. Everything is expensive.
One big problem Australia has (IMHO) is stamp duty. Stamp duty as it applies to most people is a state government tax on the sale or transfer of property. In the US instead you pay property tax (typically 1-1.5% of assessed value AFAIK). In Australia you might pay as much as 5% of the sale value in tax.
Now consider that a "normal" family home in Sydney or Perth might be $1 million. So if a family in Sydney wants to pick up and move to Perth they may be $80,000 in the hole (including agent fees and the like) before they even start... all for a job that might only pay $100-150k. This I believe really hurts labour market flexibility.
Through a combination of taxing property and not the transaction and lower overall property values, this is not a problem the US has.
I often joke to friends and family that it is cheaper for me to live in Manhattan than in Perth now.
This has several negatives when it comes to tech:
1. There is a strong incentive go to the US, Real standard of living is higher, jobs are more plentiful and so on;
2. The high cost of living makes bootstrapping a startup in Perth expensive and not very attractive. More broadly to varying degrees I believe this applies to a large part of urban Australia;
3. Perth at least has never really had a tech scene per se. The norm is for any sufficiently large company to headquarter itself in Sydney or Melbourne. The only exception are resource companies (Rio Tinto, BHP, Woodside Petroleum and the like); and
4. Because there is so much "easy money" floating around in resources it's just to justify a tech startup comparatively.
Plus there are usual reasons: Australia is far from everywhere (Europe, Australia, even Asia) and Perth is even further (it is I believe the most isolated capital city in the world and you need to go 3000 miles before you find another city above 100,000 people).
Startups don't start in a vacuum. There is an ecosystem that makes them thrive. Angel funding, VC, etc.
As far as regulation goes, I don't see any particular barrier here. Forming a company in Australia isn't cheap (~$1000 for a private company, more for a public). Financial regulation is much stricter such that operating in financial services is a difficult proposition because of regulatory burden. For example, I don't believe Mint.com could ever have started in Australia.
I largely discount the "lack" of government involvement. Businesses will grow and thrive largely independently of the government and it's not something the government tends to be good at encouraging anyway (just look at the whole Curt Schilling thing).
If I was going to do a startup today I'd go and hole up for 6-12 months somewhere cheap to get an MVP and then base myself somewhere with a decent tech scene, maybe NYC or Boston.
From what I read the housing market is just nuts in SF now. Attracting and, more importantly, retaining staff I imagine is difficult in the Valley now. So much so that I think I would skip it entirely.
Whatever the case, Australia would be pretty low down on my list.