One suggestion I'd offer is to consider not bothering with buying an unlocked phone -- just make sure that whatever you buy is a model that the unlocking services can unlock for you (fee is usually in the $30~$50 range, so it's still a lot cheaper than the unlocked versions).
You can find any number of services eager to do the unlocking for you with a simple Google search for
phone unlock.
This is the route I plan to go next time 'it's time' to change phones.
