So Deans is gone... after 5 1/2 years and 74 tests (43 wins / 29 losses / 2 draws) - a winning percentage of 58%.
Personally I think he's a victim of (a) being a NZer, and (b) Australia's proximity to NZ at a time when the All Blacks are ridiculously strong (the ABs B-side of the last few years would have taken care of most international sides, most of the time).
In 18 tests against the ABs under Deans, the Wallabies only won 3 times.
Take those 18 tests out of his record, and Dean's winning % as a coach jumps to 71%.
I understand there are some suggestions of a dysfunctional culture within the Wallabies - and that, in truth, could well be his greatest failing as a coach.
But 71% (ex ABs) isn't a bad record - considering Rugby in Australia has a lot more competition for players than Rugby in NZ does (it's institutionalised fanaticism in NZ).