This summer I flew SYD-BNE-CNS-SYD with Virgin Blue. They have an Airpass for visitors for abroad if you do 3 flights and book in advance. My three flights cost Aus $280 and included 23KG baggage + a carry on. Flight very good, and service good. 4 flight attendants with 2 carts made service fast.