Lookup field on VF page is not showing available choices on Force.com site

I have a visualforce page on a Force.com site that uses the Contact standard controller to create a new contact. I have a lookup field on the page which should pull a list of the location__c custom object. In the preview, the lookup field is working perfectly, however on the Force.com site the lookup dialog box opens and says this:

No records found due to one of the following:
There are no records of this type
You don’t have permission to see any of the records
Records do not fit the filter criteria set by your administrator

On the site detail page Search Pages and Lookup Page are both selected in the Site Standard Pages.

The profile has read and create access on the contact object and the location__c custom object.

Here is a simplified code of the VF page:

<apex:page standardController="Contact" extensions="NewContactControllerExtension" showHeader="false">
<apex:slds />
  <div class="slds-scope">
    <div style="padding-right:50px; padding-left:50px; ">
        <apex:form >
            <apex:pageBlock title="Add a New Contact">
                <apex:pageBlockSection columns="1">
                        <apex:inputField value="{!Contact.FirstName}"/>
                        <apex:inputField value="{!Contact.LastName}"/>
                        <apex:inputField value="{!Contact.Building__c }" required="true"/> <!--This is the lookup field -->
                </apex:pageBlockSection>
                <div style="margin:auto;">
                    <apex:commandButton action="{!saveAndRedirect}" value="Save"/>
                </div>
            </apex:pageBlock>
        </apex:form>
    </div>
  </div>
</apex:page>

This is the code for the controller extension (which just saves and redirects the page when user clicks save button):

public class NewContactControllerExtension {
private Apexpages.StandardController controller;
public NewContactControllerExtension(ApexPages.StandardController stdController) {
    this.controller = stdController;
}
public PageReference saveAndRedirect() {
  controller.save();
  PageReference newPage = Page.ThankYou;
  newPage.setRedirect(true);
  return newPage;

}
}