Another vote for YNAB. If you are looking for free, would something like yodlee , mint, or personal capital work with AUD? I would think so since it just links to your existing accounts. But they are really more like tracking tools, not budgeting tools.
I suggest checking out a webinar to see how the software works, then try the trial. I have admitted before it took me more than 34 days to really start liking it, but I bought it fairly discounted and thought at the time it was work a try for the price.