I would go to the CX counters on the arrival level located between Bays 1 and 21 before clearing immigration and customs. Smile as sweetly as you can and check the situation for the Melbourne flight. If it is wide open they may just give you a boarding pass. In that case they can retrieve your bags from the carousel and re-tag for Melbourne.
If no joy there, clear immigration and customs and trudge up to the queue upstairs.