Please check that you do not have a contacts start up tag filter on, if so this could be why you are unable to find contacts using the search options.

If you click on the main Contacts icon inside your account you will see if you have a tag filter on your contacts as these will be shown with a red X beside each tag group you have filtered - as shown below in red:

To remove any of the tag filters just click on the red X beside each tag name:

This will remove the tag filter and all contacts in the database will then be displayed.

You can then search on the different drop down menus as shown in the example below:

If you wish to remove the contacts startup tag filter permanently you will need to remove this from inside the Settings where you set the tag filer up. 

Click on the Settings icon along the menu bar 

This will open up the following window.  If you remove the tags that are listed in this field as shown below and click on Update Settings this will remove any tag filters in place.