Please follow troubleshooting and turn on WP_DEBUG and send us the debug log from your import attempt. If CiCi can import but you cannot there is likely something specific to your PHP settings or something else in your environment that is conflicting with the import.
As for performance of the search itself, please try upgrading to the latest version of the Power pre-release. There is a performance patch that has a big impact if you have more than 1,000 locations. I’d like to know if it addresses search issues in the real-world versus my test environment before releasing to production. It is pre-release so please make sure your site is backed up first or run it on a staging version of your site.
CiCi can send the prerelease of Power if you cannot get it from your downloads. I believe the performance patch is in Power 4.5.11.