If you would re-read my posts above - you'll understand that I placed your BD search widget before created the page with shortcode - this is the reason of the problem. This bug is in the structure of your script, you allow to add widgets before creation of the page with shortcode. The same issue raises when I tried to preview new directory listing.
I am not doing any customizations, this is WP and BD plugin from the scratch (you may easily found this thing from my messages above).
Also you didn't mentioned such thing that the page with shortcode really REQUIRED in you installation instructions: http://businessdirectoryplugin.com/docs/#install
I just inspect your code, and, by the way, found other much more serious bugs. "much more serious" because they do not related with installation stuff, but may affect already working site.
And finally, fix this bug in wpbdp_get_page_link() function, when there is any chance to run into infinite recursion - this is really bad style of coding.