I just spotted this article in Time magazine that describes a "world phone," a device that conforms to an international standard for worldwide reception. The writer tested two models: Samsung V205 from T-Mobile and Sony Ericsson T68i from AT&T. Both services were quite expensive (surprise!), but the reviewer was pleased with both.
Both devices also let you check email and take/send pictures.