Pagination links don't work when you have a get parameter added to them on sites with permalinks enabled, the url is set to ?something=true/paged/1 instead of /paged/1/?something=true
Just came across this. I'm using the RTL Tester plugin, which adds a d=rtl or d=ltr query string parameters. The blog archive pagination links therefore try to load example.com/blog?d=ltr/page/2 which obviously fail.
(potential) alternative fix for loop pagination issue
Alternative fix for loop pagination issue described here: justintadlock#56
Based on get_pagenum_link() usage described http://www.kevinleary.net/wordpress-pagination-paginate_links/ and in the codex at http://codex.wordpress.org/Function_Reference/paginate_links#Examples
This worked in my situation.
Fix for Loop Pagination bug. Fixes #56 and #81. Props @jconroy.