mmars has it right. It really is hit and miss.
Whenever a new issue is released, the Scotiabank main commercial branch in downtown Vancouver has always had them ready for me on the first day of issue. At other times, the branch may or may not have brand new notes available. My credit union never has new notes; they claim that they get all of their cash from customer deposits only.
I believe that any chartered bank has the ability to order new notes from Bank of Canada regional offices. Whether or not branch staff are aware of this or not, or if they are willing to do it for you even if they are, is highly variable.