Why Does SharePoint Search not find some sub-sites?

I have set up an Enterprise Wiki sub-site (one level down) to a site collection. But when I try to search for it from the main SharePoint.aspx page, it is not found. I have waited a number days in case it is is because the site had not yet been indexed. I have also made sure the site 'Search and Offline Availabilty' is set to 'Allow this site to appear in search results' and Indexing ASPX Page Content is set to Always index all Web Parts on this page. But the site is still never discovered in any search. Does anyone have any insight as to why this may be?

Thanks,

Natalie