Something rugged is a good idea.

The Pentax Optio WP is rugged and waterproof. Unfortunately the small fixed lens is limiting (though will probably crush anything built into a cell phone).
http://www.dpreview.com/news/0501/05010501pentax_optiowp.asp

Olympus has the Stylus series and some other small cameras that are weather/dust resistant and should also be considered.

http://www.dcresource.com/reviews/olympus/stylus_500-review/index.shtml

I just ordered an amazing little camera from Panasonic (DMC-FX9).
http://www.dpreview.com/news/0507/05072002panasonic_fx9.asp

It has 3x optical zoom with stabilized optics. I don't think any other pocket camera can compare. I currently own the Panasonic DMC-FZ5. The stabilized optics in this camera has allowed me to take pics that would have been impossible otherwise. The FX9 is probably not as rugged as the Optio or Stylus, so I will be sure to pad it adequately. I am starting with this made in Australia, full cover, custom fit case I found on eBay.
http://search.ebay.com/_W0QQsassZatomichh

If size is not an issue, I'd say look for one of the small cameras that still use AA batts so recharging is not a concern.

Good luck, TR