Well firstly, IB is a very good airline for J availability from MAD - JFK, even well after the release date IME, so I'd be trying another QF operator as the one you spoke to must have made a mistake.
I presume you know that most AA domestic services are 2 class - Y and F - so on a J award you get booked into Y and it's useless to be asking for J seats. There is J class on the CUN - DFW flight but, having flown it last year, I can tell you that the J on that route is pretty ordinary. AA is getting more difficult to get award seats on since the start of this year - although they are supposed to be released at 330 days, they frequently don't show up until about 300 days out. Maybe do a few dummy searches for dates about 300 days from now to see if you can get an idea of when AA are posting awards on that route nowadays.
DFW - LAS can be a problem now too - if you do get awards you can expect that AA will only give you indirect options through PHX. AA really have tightened up on award availability on direct flights between the major cities, unfortunately.
You very likely won't get award seats (it will be in Y) from LAS - LAX on either a Sunday or a Monday - I think AA don't release them because there is strong demand from paying customers wanting to get home after a weekend in Vegas. Tuesdays to Saturdays should be OK if you can modify your dates.
And finally, CX blocks some connecting flights through HKG i.e. you might be able to find J availability on each of the LAX - HKG and HKG - MEL legs but you usually won't be able to get them as connecting flights with a less than 24 hrs transit in HKG. At this stage you're unlikely to get any LAX - MEL direct flights as an alternative to going through HKG but I'd be looking at anything from LAX or DFW to MEL, BNE or SYD. In the end you might have to accept that you could have to pay for a couple of US domestic flights just because it might prove impossible to get any workable solution for awards.
