I was filtering posts on a single page with the function call 'query_posts' and noticed after a while the same problem as the original poster (Dunkkan) - the unabillity to sift through older and newer posts with the next_posts_link or previous_posts_link call, and it was easily addressed to the query_post function, since if I turned it off, everything worked fine.
this seems to solve it. I'm not sure for how long though, since I'm quite novice to php and wordpress altogether. I make of use of the get_query_var and dynamically add the appropriate paged number to the offset variable.
//get the categories...
$submissions = get_cat_ID( 'submissions' );
$inspiration = get_cat_ID( 'inspiration' );
$finalist = get_cat_ID( 'finalist' );
$crew = get_cat_ID( 'crew' );
$offset = '&offset='.((get_query_var('paged')-1)*10);
$offset = '&offset=0';
$querystring = 'cat='. $submissions.','.$inspiration.','.$finalist.','.$offset;
<?php query_posts($querystring.'&showposts=10'); ?>
<?php if (have_posts()) : ?>...
...<?php endif; ?>
<?php wp_reset_query(); ?>