The field is frankly rather small if they are looking for major Australian sponsors; ie major corps with international exposure/looking for increased intl exposure.
Santos (energy) already has naming rights with TdU and I'm not sure they'll want to expand beyond that. Most other energy/mining have steered away from major sponsorships.
That does basically narrow it down to QANTAS & the "big four" domestic banks. It MAY be an interesting prospect for QANTAS however, as a previous poster highlighted, their bottom line hasn't been the best lately so they may pass ... at least as primary sponsor.
The banks ?? ANZ & NAB have involved themselves in medium-longer term sponsorship deals with sport in Australia .... albeit with Olympic sports. Westpac .... no real background. Commonwealth Bank used to sponsor the Commonwealth Bank Cycle Classic which was a major amateur race along the east coast of Australia during the 80's-early 90's (used to pull some v strong teams incl the eastern bloc). Commonwealth is, however, less internationally focused than the other three.
Unlike many of their counterparts in the US & UK, these banks ARE in sound condition and, whilst not the most ideal climate to be sponsor-shopping, I feel they would be the most likely prospects.