Kevin Rudd was voted in with high popularity. However, most people thought he was too far right when it came to some issues (labour rights and education among others) and others thought he was too soft on other things (asylum seekers among other issues, despite him being as far right on this issue as Howard).
Then he brought in the Emissions Trading Scheme, and he called global warming something like the greatest challenge of our time. Then he dropped when he didn't have enough support, and that left a sour taste in people mouths.
Then comes the mining tax. The government needs the money, and so the tax on "super-profits" made by mining companies is raised to 40% in the short term, and company tax will be lowered to 27-28% in a few years. Mining companies were furious, and launched a massive campaign against it, and unfortunately people were fooled into believing them, despite many economists in Australia and around the world praised the tax.
Anyway, Julia Gillard is much the same as Rudd, but she has much better PR, and therefore gives the Labour Party a chance to win. Otherwise, they're all pretty much the same.