Upgraded from 4.01 to 4.02 (didn't have to run upgrade.php, is that correct?) The problem is still there.
As a guest, I go to our classifieds section, I select page 2 at the bottom, and the problem occurs. This doesn't stop me from going back and using the classifieds as normal though.
However, when I am logged in and the problem occurs, it doesn't go away until after I log out and clear all my cookies, so this makes me think it's a cookie problem.