Contact Fido. If anything, they may let you know if doing so would flag an early cancellation fee on voice and/or data.
Other options would be to buy a phone you like outright (from Fido or any other carrier) and use that with your current plan. But if the phone is bought from another carrier, you may need to be unlock it to work with Fido.
As sonyandroid pointed out, you can also consider an Android. There's also Windows Phone 7 as another possible alternative. This will be dependent on your what your preferences are.
