It's no doubt a VERY political process. They will likely not be interested in working with you unless you have a ton of users or will pay for the time they need to integrate with whatever system you build and even then I'm sure it'd be hard to convince them.
I'm pretty convinced that the only way to have a phone that will work in EVERY country, for now, is to get a satellite phone which has a moderate up front cost and a comparatively significant marginal cost (per minute).
Good luck though!
Disadvantages / Problems: I'm sure there are some so feel free to add. The main obstacle that I can think of is that you might have to contact and create relationships with all the network providers around the globe, which may be a very political process. I don't have much knowledge in this area but maybe someone in the mobile industry could fill in the possible setbacks and problems related to the mobile industry.