Mr. Red: Scott Balfour's Alice Springs group, Bloodwood, recorded Waltzing Matilda to another tune, cited on the CD as "traditional." It is bouncy and a good fit; might this be the one you mean?
Of course one of the national pastimes of musician friends down under seems to be new words to old tunes and rearranging lyric/tune pairings.