“Previous entries” link leads to 404

Eversince I installed a new WP theme, the link to Previous Entries lead to a 404 Not Found page. Even if I directly paste the URL (eg., http://www.bandstalker.com/index.php?paged=2) on my browser, I still get directed to the 404 page. What could be the problem and how am I going to resolve it? Thanks.