A few months ago, I used a loaner Blackberry for a week or so. When I was bored and fiddling around with it, I discovered the "saved messages" folder on the device had about a dozen e-mails in it from a previous user. Not good. I deleted them all and then did a bit of research to make sure that I didn't leave any data behind when I returned it.
This has just happened on a massive scale, according to Schneier on Security. He's blogging about a recent incident that has more than a few cellular customers hopping mad. When trading up, customers of a certain cellular provider were asked if they wanted to donate their older phones to charities, such as local women's shelters. The phones ended up on e-bay and the company didn't even bother purging the phones of data. Not good in more ways than one. See Schneier on Security: Privacy Risks of Used Cell Phones.