You said that you are taking all necessary measures and that you have adequate staff, etc. I tend to believe you. However, in reality, we do not get the impression that Air Canada is interesting in serving the francophone population in French. Perhaps that is simply a perception, but all of us could give you specific examples of what is not working. Perhaps we have to approach this differently.
For example, you said that there was always a flight attendant on board who can speak French. I recently travelled on a plane and I was spoken to in English. I therefore made an effort, as the client, and continued to speak in French. Someone was brought to me who could speak French, but throughout the rest of the flight, it was the anglophone employee who dealt with me. In other words, the staff made no extra effort to serve me in French. After they have realized that a client wishes to be served in French, they forget. Perhaps that's where some adjustments need to be made.