CiviCRM Full-text Search' block - Returning Error: Error type: Could not find a valid session key."

When using the CIVICRM Full-Text Search Block I get the following:
[Sorry but we are not able to provide this at the moment.
We can't load the requested web page. This page requires cookies to be enabled in your browser settings. Please check this setting and enable cookies (if they are not enabled). Then try again. If this error persists, contact the site adminstrator for assistance.

Site Administrators: This error may indicate that users are accessing this page using a domain or URL other than the configured Base URL. EXAMPLE: Base URL is http://example.org, but some users are accessing the page via http://www.example.org or a domain alias like http://myotherexample.org.

Error type: Could not find a valid session key.]

If I add http:// in front of the URL the search results come back correctly. Also the Advanced Search works correctly only the built in block is an issue.

Just wondering where the http:// gets setup and how to correct it so the block works and returns the results as does the Advanced Search.
Thank you,