Weird permalink problem

I’ve got this weird problem when I try to use permalinks on my blog, everything works just as expected, except when I try to go back a page or two then I get a very unexpected 404 error. From the front page I can go one page back before hitting the 404, while on the category page I get the 404 when I click the “previous posts” link the first time.

Switching to another theme doesn’t help, but if I turn off permalinks it works perfectly fine. Anyone out there that can help me?