My research suggests that themes which return invalid XML during the search will run into this problem.
The most likely cause on invalid XML coming back is that your theme (or a plugin) is adding whitespace to the top of the XML file.
An easy way to debug is to just View Source of any page in your dashboard - is there whitespace at the top of the source code? If so, this is likely your problem.
This can usually be addressed by removing the closing ?> tags from your theme's php files. If that alone doesn't do it, try to narrow down the source of your extra white space and resolve it.
Plugin Author: This looks to be a somewhat common problem with people using your plugin. Perhaps you can apply some sort of trim() function to the XML that comes back before validating it?