Kra, eu tava tendo o mesmo problema que o seu. Consegui resolver agora mesmo.
Eu vi que colocando o valor no paged, ex: 1 ou 2.. ele retornava os posts corretos das paginas.
Então na sorte mesmo, concatenei a variavel e ai.. vualá.. funcionou.
Coloquei a linha assim:
query_posts(’cat=4&posts_per_page=10&paged=’.$paged.''); ?>
Espero ter ajudado.
