Advanced Search Results Pagination not working correctly

If you use two words. If you use one like Leather, that works. Try leather bracelet and it works to pull the results but you can't go to subsequent pages. When the advanced search page shows up, the blank includes this: leather%252520bracelet

This site has no changes to the search function so what can be causing this?

I did notice that even though the database has been converted to utf-8, there are still some oddities of characters showing. I don't know if this could have anything to do with it.