What permissions must I secure to be able to offer a celebrity photo
as a download to a mobile phone as a screensaver or wallpaper?  If the
photographer's permission has been secured, or the photo is made
available from a "clearing house" source, is permission from the
celebrity still required?  What is the definition of celebrity - how
far does it extend beyond music, sports and entertainment stars (is
Bill Clinton a celebrity?  was Pope John Paul II a celebrity)?

Assuming that the images of celebrities have some aspect of commercial
use associated with them, you would not only need to license the
photograph, but also obtain that celebrity's permission.  This is true
for every human being, regardless of whether or not they are a
celebrity.  However, unauthorized use of a celebrity's image is
particularly risky because "...there is often a comparable market
against which to measure the celebrity's value."  This can lead to
very high damages when authorized users pay significant sums for that
individual's likeness.

Use of a photograph in a publication in connection with an article is
considered to be a different form of use that merely requires the
photograph to be licensed.

Sources:

"Dr. X Will Build a Creature" By Jim B. Astrachan, Astrachan Gunst
Thomas, P.C. (May 16, 2004)
http://www.agtlawyers.com/thefirm/newsitem.php?item=114

"Celebrity-Likeness Law: What it Means" By Katherine Hendricks,
Hendricks & Lewis (June 1998) http://www.hllaw.com/a_celebrity.html

"Right of Publicity" by Lloyd L. Rich, The Publishing Law Center 
(2000) http://www.publaw.com/rightpriv.html

"Do Tiger Woods, Dustin Hoffman, and Other Celebrities Owned
Information About Themselves?"  By Krista L. Witanowski, American Bar
Association (Spring 2002)
http://www.wrf.com/docs/publications/11621.pdf
Search terms: license celebrity likeness