I have been facing a similiar issue with shipping! I manage the website for a retailer: www.funsockcity.com I wanted to set up a new flat-rate price for shipping to Canada. So, like most of you, I moved Canada to a seperate zone. I made sure the provinces (or states) were moved to this new "Canada" zone. I set up my price range and now my shipping to Canada is coming up as the same rate as my doemstic shipping (which is the US).
I have been digging on Forums, search Google, and I cannot find a fix for my particular issue.
I am using PrestaShop 1.5.2.0.
If anyone has any suggestions, I would greatly appreciate it, as I am starting to go kind of crazy trying to figure this issue out.