Typically in extraditions, the treaties will only allow for extraditions if both nations have a similar crime and similar punishment for that crime. In this case, there maybe some pause for Australia to grant an extradition as Australia no longer has the death penalty for any crime, so it could be that while the new crime the defendant is being sought for is Escape from Incarceration related (that's a yes in both countries), technically the punishment for an escaped Death Row Inmate is the Death Penalty. Australia can't extradite for any crime where death penalty is on the line, but the requesting nation can say they will give a more lighter sentance that is more compliant with the requested nation's own laws. However, since it is Death for another crime that Austrilia never had jurisdiction over, it complicates matters. There is precidence for procedural reasons for refusing to extradite.
For example, while the U.S. and Italy have an extradition treaty and both view murder in the same light, the U.S. refused the extradition of a citizen who was wanted for a murder in Italy that she was previously aquitted of, but new evidnce was uncovered. Because it is illegal for the state to try a person twice for the same crime in the U.S., the U.S. declined the extradition treaty.
Some additional notes, extradited persons can only be tried for crimes that they were extradited for, so there is an argument that Australia would refuse unless Indonesia promises to commute the Drug Trafficking sentence to Life Imprisonment