Ok, I made a function to provide this. If somebody searches for this topic, here you have:
function bring_previous_next_post_link($previous, $template, $text, $cat) {
global $post;
$original_post = $post;
query_posts($cat);
$posts = get_posts('offset=0&orderby=menu_order&order=ASC&numberposts=1000');
$link = '';
$gotThere = false;
foreach($posts as $post) {
start_wp();
if ($post->ID == $original_post->ID) {
$gotThere = true;
} else {
if ($previous && $gotThere) break;
$link = get_permalink();
if (!$previous && $gotThere) continue;
}
}
echo str_replace("%link", "<a href='".$link."'>".$text."</a>", $template);
$post = $original_post;
}