I think bumping this thread might be better than duplicating it.
I've also had this problem, and it's easy to recreate, even with a tiny address book (minimum 2 entries):
1) Go into Personal Settings and change Rows per page to 1 (yes, one!)
2) Go to the Address Book and click the |> arrow to load the second page/contact
3) Select the contact on the second page and Click 'Compose Mail to'
This generates the 'No Contacts Found' error as described by pt1xoom.
Resetting the 'Rows per page' entry to something high provides a workaround of course, but is not a solution.