I just had the same issue. I found that when i placed my cursor in the search field there was a space already in there before is started typing anything – test this yourself by clicking in the search input, hitting delete and then typing your search term. It should work.
I opened my themes search form and found i had a space in the value field that was causing the + issue.
<input class=”text” type=”text” value=” “ name=”s” id=”s” style=”float:right;” />
Delete the space and save the file and this fixes the issue.
Please note this is the actual theme search form php file not any file within the plugin folder.
