The Wall St Journal today had a feature on services that let you do Skype-type of calls from your cell phone. The article is here, although I'm not sure non-subscribers can access it.
The article really wasn't clear about whether your phone has to have Internet access to use these services, or whether some of them work via placing a call on the phone network that is then transferred to the Internet. The article especially focuses on Truphone, which has an application for the iPhone that you can use via wi-fi. (Of course, you have to be someplace with wi-fi access.)
If anyone has used any of these, let us know how they work.