I am a T-mobile customer and up until now I was very happy with their service. The only reason I do not have an iPhone is because I did not want to go to ATT. Now, I have no choice but to go with Verizon, and I will.
Yes, the problem is the different 3G band. Otherwise, you can just buy a unlocked iPhone from France (without having the jailbreak it). Obviously, this makes sense only if you go to France for other purposes.