TupiLabs website uses Wordpress as backing CMS and blog, and here we have a modified Roots theme with bunch of plug-ins and settings. The pagination of the posts is done with WP-Pagenavi plug-in. When we received a message from José saying that the pagination was broken, we thought it had something to do with WPML, a translation plug-in, used to maintain both languages (en and pt_BR) in the site.
Later we figured out what was causing this error. The error happened only in pages that list categories (blog, news and ideas). In these pages, the function query_posts was being used, and after googling a while we found out that there was an extra argument for pagination.
query_posts(array('category_name' => 'blog'));
Changing the line above to:
query_posts(array('category_name' => 'blog', 'paged' => get_query_var('page')));
Fixed the issue. We also use plug-ins for cache, so we had to purge the pages from the cache in order to see the results. Hope that helps you, in case you have similar problem. Cheers.