Personally I think there are too many CEO's out there who receive pay checks well above their actual value to the company. I also think that a CEO's pay should be directly linked to the company's bottom line (make it really nasty, make it based on amounts after tax and "schemes", let's see how happy they'd be with creative accounting then). Company does well, CEO does well, company does badly, well I hope the CEO likes living on baked beans.
All that said, the amounts given to AJ / JB are not exactly on the extreme scale for a CEO, even in AU. Considering that as a business both are doing ok (as ok as any airline can do) I don't exactly see the problem.