If you're interested, you could read up on the "constitutional crisis" of 1975:
http://en.wikipedia.org/wiki/1975_Australian_constitutional_crisis
If a bill can't get through the senate, they have to negotiate in order to get it through. It is quite rare for a single party to have a majority in the senate, so this kind of negotiation is the norm. If the government fails to get a bill through the senate on multiple attempts they can call (or, technically, "request") a "double dissolution" election, which means that the whole senate is up for re-election as opposed to normally just half of it. We haven't had one of those since the 80s. If the Greens and Labor have a senate majority in the new senate, we may be up for one again next year, depending on how hardline Abbott wants to get about pushing his stuff through. The senate result is hard enough to predict, let alone what goes through that mans head, so we can't really say yet.
As for changes, at the very least we need to change the way senate voting works. We have a preferential voting system for the house, but for the senate we either choose one party, or have to number every single candidate, which is as high as 110 this year. If you vote for the single party, because of the weird way senate votes are counted, they choose their own preferences, which can be a little weird and not what you really want. 95% of people vote for the single party though. This needs to be improved.
One of our state governments eliminated the senate. I won't talk about state politics too much, but see what happened in Queensland since the last election, I would never want to get rid of the senate.
As far as pie in the sky changes that will never ever happen goes, I think they should abolish state governments. It's an extra layer that we don't need.