All your working conditions can be changed with enough notice in Canada as long as you don't fall below the minimum standards in most cases. In particular, this applies where the employer provides discretionary benefits and reserves the right to adjust these benefits in its employment contract (normally the case).
If the change is great enough to allow for a claim of constructive dismissal the remedy is the same amount of notice as would be necessary for a termination. The real issue is employee retention. Turn-over costs a lot and good employees are a valuable asset.
This is not; however, true if you are part of a union and you have negotiated set terms of employment. You will need to renegotiate these contractually agreed-upon items upon expiration of the collective agreement.
This is also not true if you are a term employee on contract. Your contract cannot be changed prior to end of the term unless there is language in the contract to permit this.
This is also not true if prior to hire you negotiate separate terms from the employer's employment policies. This is unusual.
For IBM, reading their union complaints page, I gather that timing of payment of the benefit was not part of the negotiated contract.