Yes, it will solve the problem.
Speaking about the page structure, I see that the q2a author has applied exactly what google is suggesting to do with a pagination. Have a look here :
http://googlewebmastercentral.blogspot.it/2011/09/pagination-with-relnext-and-relprev.html
If you view the source of a page, for example this one :
http://www.9comp.com/qa/unanswered?by=upvotes&start=14
you can see that, in the head section, the 2 next/prev links are present :
<LINK REL="prev" HREF="./unanswered?by=upvotes&start=0">
<LINK REL="next" HREF="./unanswered?by=upvotes&start=28">
Google says that they are only a strong hint, and not not a mandate : ok.
But they should work....
I've only a doubt about the href value : "./unanswered?......" used in the page code.
I think it should be better to put here an absolute url or a relative url with a <base> link in the head, as google is suggesting in the article.
I think this could be a (the) problem....
If the rel=next/prev hint was working, you should not have to change the title of your pages in the pagination, because google bot would understand that they belong to the same series.