The short answer is that AC is legally responsible to follow the exact T&Cs set forth in this AD. Below I have set forth the reasons why AC has to follow it.
The impact of an AD depends on the condition set forth in the AD. A few background notes:
1) In order for an aircraft to fly, it must be in possession of a valid Air Worthiness Certificate. As summarized nicely on Wikipedia:
A certificate of airworthiness (CofA), or an airworthiness certificate, is issued for an aircraft by the national aviation authority in the state in which the aircraft is registered. The airworthiness certificate attests that the aircraft is airworthy insofar as the aircraft conforms to its type design. Each airworthiness certificate is issued in one of a number of different categories. A certificate of airworthiness is issued when the aircraft is registered in the name of the owner. Thereafter, a yearly currency fee is payable to renew the Certificate of Airworthiness. If this fee is not paid when due, the certificate expires and the owner must apply again for this certificate to be issued. The Certificate of Airworthiness can only be issued when a certificate of release to service from the maintenance facility declares that the maintenance due has been carried out and the aircraft is then certified as being airworthy.
2) Also from Wikipedia:
An airworthiness directive (commonly abbreviated as AD) is a notification to owners and operators of certified aircraft that a known safety deficiency with a particular model of aircraft, engine, avionics or other system exists and must be corrected. If a certified aircraft has outstanding airworthiness directives that have not been complied with, the aircraft is not considered airworthy. Thus, it is mandatory for an aircraft operator to comply with an AD.
To summarize the two points above: if the conditions of an AD are not met, the aircraft is not considered airworthy. In this case, in order for Boeing 777-300ERs under the FAA's jurisdiction to remain airworthy, the operators are required to:
Within 25 flight cycles after the effective date of this AD, remove from service the Interstage Seal, part number 2505M72P01 with serial numbers GWN0TCL3, NCE062LD, NCE254LC, NCE314KU, NCE374LB, NCE527KT, NCE777LD, or NCE994KW.
.
Even though this AD is issued by the FAA for American registered aircraft, in Air Canada's case they are also required to comply with this AD as Canadian Aviation Regulations 605.84 "recognizes the mandatory status of foreign ADs and equivalent notices issued by the aviation authority that has jurisdiction over the type design of the aeronautical product". This means that if the aviation authority has jurisdiction over that specific type design, then the AD must be followed in Canada. In even simpler terms, if the US puts and AD on a US product, Canadian registered aircraft have to follow it. If the US puts an AD on a non-US product, then Canadian registered aircraft do not have to follow it. The FAA is responsible for the type design of the Boeing 777-300ER, therefore the AD is mandatory for Canadian registered Boeing 777-300ERs, and AC must comply with the AD before their aircraft hit 25 cycles after the receipt of this AD.