Пол дня ушло на поиск решения, в итоге ответ спрятался в кодексе, причем в описании самой query_posts();
Pagination #Pagination
Pagination won’t work correctly, unless you set the ‘paged’ query var appropriately: adding the paged parameter
Добавить параметр 'paged' в запрос и все работает.
query_posts ("cat=3&orderby=date&paged=".$paged);
