Capybara : StaleElementReference Error Element not found in the cache

Capybara : StaleElementReference Error Element not found in the cache

I'm using Capybara 2.1 with Ruby 1.9.3 using the selenium driver (with
Minitest and Test Unit) in order to test a web app.
I am struggling with the StaleElementReferenceException problem. I have
seen quite a number of discussions on the topic but I haven't been able to
find a solution to the issue that I am facing.
So basically, I'm trying to find all pagination elements on my page using
this code :
pagination_elements = page.all('.pagination a')
Then I'm doing some assertions on those elements like :
pagination_elements.first.must_have_content('1')
After those assertions, I'm continuing the test by clicking on the Next
Page link to make sure that my future first pagination element will be the
Previous Page. To do that I'm retrieving paginations elements again :
new_pagination_elements = page.all('.pagination a')
And the Stale Error is occurring here, because I'm reaching elements that
I've already reached. ( Here is the error )
You can see the link states here.
I really have no idea how to make this common test work properly. Do you
have any tips for a better way to reach my pagination elements?
Thanks in advance, Tbo !