Most Providers (probably all Providers on this site), use Telstra ADSL broadband infrastructure to sell ADSL Plans. Therefore, are usually able to offers ADSL plns everywhere that Telstra do.
This cannot be said for ADSL2+. Some Providers use Telstra's (BigPond's) ADSL2+ equipment to offer ADSL2+ plans (usually at an expensive price like ADSL), while others install their own DSLAM equipment at exchanges and by doing so, can offer ADSL2+ cheaper.
Keep in mind that Telstra do not allow competitors to use or install ADSL2+ euipment in all their enabled exchanges. This is currently what the big stink is about. Telstra monoplize the industry effectively holding Broadband to ransome as far as competition goes in Australia. They make it extremely difficult and expensive for competitors to offer value for money of quality broadband.
An telephone exchange like Cairns is still considered fairly remote, therfore ADSL2+ will be likely to be unavilable outside Bigpond. Most major metropolitan (typically capital cities) usually have alternative Providers for ADSL2+, but that's about it.
A few major Providers (like most of the ones on this site) will offer adsl services in Cairns. It's difficult to get precise indications but the best place to start is on their website by undergoing a telephone number check. Next best is then to call them. My recommendation would be to choose the best adsl plan from this site that suits your profile and simply call them, then take it from there.
Good Luck.