I would go for 7-11's free phone deal, a Nokia 1600b. Then I'd buy a new quad-band unlocked GSM phone from someone like http://www.puremobile.ca/ That will cost you another $100 or so, but (a) you can sell the 1600 on eBay (or keep it as a spare; it's unlocked so it will also work with Rogers, Fido, T-Mobile and AT&T SIMs on prepaid plans) and (b) your phone will now work in NA, OZ, Europe, etc. (with appropriate SIMs, of course.)
You should be able to get $50 for the 1600 so the cost of the quad-band phone will be only about $50. And it will probably be a much better phone too, e.g. with camera, MP3 player, bluetooth, etc.