No entendí porque tienes esta parte:
Código PHP:
Ver original<?php //para mostrar el primer post diferente
$page = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts("paged=$page"); ?>
Si quieres saber si está "paginado" (o sea $paged > 1) la llamada a
is_paged() que ya usas es suficiente. Con el código que te mencioné estás haciendo
otro query innecesario y es lo que impide que funcione para las categorías.