How to look-up a contact's name from their phone number on Android?

Yes, this is possible using ContactsContract.PhoneLookup.CONTENT_FILTER_URI in Android 2.0 and higher and Contacts.Phones.CONTENT_FILTER_URL in Android 1.6 and earlier.

For example usage, see the documentation for ContactsContract.PhoneLookup. Excerpt below:

// Android 1.6 and earlier (backwards compatible for Android 2.0+)
Uri uri = Uri.withAppendedPath(Contacts.Phones.CONTENT_FILTER_URL, Uri.encode(phoneNumber));

// Android 2.0 and later
Uri uri = Uri.withAppendedPath(ContactsContract.PhoneLookup.CONTENT_FILTER_URI, Uri.encode(phoneNumber));

// Query the filter URI
String[] projection = new String[]{ PhoneLookup.DISPLAY_NAME, ...
Cursor cursor = context.getContentResolver().query(uri, projection, ...

UPDATE: The format of the phone number does not matter. Comparison is robust and highly optimized on Android; it's done using a native sqlite function named PHONE_NUMBERS_EQUAL. For more details, search the codebase for this method. By the way, I'm not certain if it's safe to use that function directly in your own apps, but I wouldn't.

Here's what I did

ContentResolver localContentResolver = this.mContext.getContentResolver();
Cursor contactLookupCursor =  
   localContentResolver.query(
            Uri.withAppendedPath(PhoneLookup.CONTENT_FILTER_URI, 
            Uri.encode(phoneNumber)), 
            new String[] {PhoneLookup.DISPLAY_NAME, PhoneLookup._ID}, 
            null, 
            null, 
            null);
try {
while(contactLookupCursor.moveToNext()){
    String contactName = contactLookupCursor.getString(contactLookupCursor.getColumnIndexOrThrow(PhoneLookup.DISPLAY_NAME));
    String contactId = contactLookupCursor.getString(contactLookupCursor.getColumnIndexOrThrow(PhoneLookup._ID));
    Log.d(LOGTAG, "contactMatch name: " + contactName);
    Log.d(LOGTAG, "contactMatch id: " + contactId);
    }
} finally {
contactLookupCursor.close();
} 

Passing in your phone number you already have into Uri.encode(phoneNumber)