I have a client using WooCommerce with Wootique theme. When a search is performed, the paged results are returned and page renders fine. If you click on Next or "2", a 404 error is raised. I also noticed that the search box now contains the 3 words entered but the space is missing. Is this the key to the problem?
Here is an example that shows page 1. Click on "Next" or "2" and you will get the 404:-
This is an issue with the Woo Framework. Update that, and if no luck post on http://support.woothemes.com .