The code that Kafkaesqui provided will not page correctly if Category’s showposts (in this case, 2) differs from the general posts_per_page set in Admin (say, 5). I also have this problem on my WordPress.
Say Category 3 has 11 posts, and we want to implement the code to show 11/2 = 6 pages. If the general posts_per_page in Admin is set to 5, the code will only generate 11/5 = 3 pages. When you click through the links, the latest one and two posts will show on the first page, the latest three & four on the second page, and the latest five & six on the third page. However earlier pages will not be linked.
I have tried setting posts_per_page in query_post:
<?php
$page = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts("cat=3&showposts=2&paged=$page&posts_per_page=2");
?>
Too bad that the problem persists.
What do you think, Kafkaesqui?