Multi-Term Search: 2nd, 3rd, etc. pages of results broken

When using a multi-term search (e.g. “two words” with or without quotes), the first page of results displays correctly, but if I try to view the next page (using the Next or page number buttons at the bottom), there are no results found.

I think this is related to the URL:
On the initial search results page, this is correct: http://mysite.com/wordpress/?s=two+words&submit.x=0&submit.y=0&submit=Go.
On the second page, it changes to: http://mysite.com/wordpress/search/twowords/page/2/

The site is on WP 3.4.1 and using a theme (Canvas) from WooThemes. I’m using the default WP search, but I also tried installing Relevanssi and that did not fix the issue.