I think most providers will let you change your plan as long as the replacement is at least as expensive as the plan that qualified you for the phone subsidy. I have switched plans with Clearnet, and then Telus, several times while I was under contract, without penalty.
To qualify for the free Blackberry Pearl, one had to have a minimum $30 voice plan (before SAF, 9-1-1, etc) AND a $15 data plan (includes everything so there is no option to upgrade. For me, the $30 voice plan is part of a family-plan so I share the daytime minutes with my partner who then only pays $10. With unlimited evenings and weekends, which Telus bonused us at no charge because I've been a client since Clearnet, and free calling between us wherever we are in Canada, we have all the minutes we need. However, if I was to attempt to downgrade the plan, I would expect to encounter some objection from Telus.