Go to next page not working

I have 4 categories in the site. When going to the listing category of each page all is well except one. Which happens to be the one with the most items. When page two is clicked I get Nothing found along with the following message:

This is somewhat embarrassing, isn’t it?
It seems we can’t find what you’re looking for. Perhaps searching can help.

How can I fix this?

Thanks in advance!