wrt phone/SIM compatibility (1) I assume that your phone was unlocked, but Canadian phones were sold locked until fairly recently. IIRC, can be unlocked for free if you ask your carrier (2) if this is still an issue for you, you can get the list of frequencies supported by your phone and cross-check with those from foreign networks. Very very unlikely to be the problem, however.
wrt routing -- there are several alternatives. Locus Pro has a store where you can purchase maps for a nominal fee. Free is nice but when a map is optimized and up-to-date for a couple of bucks...I've downloaded maps for most of the world but I typically purchase/update the map(s) for the destination where I am planning to tour. Fewer surprises.
take care