get_adjacent_post() returning weird results

I am using get_adjacent_post() function to display links to a previous and next post. It is a custom post which also has a custom taxonomy.

This is the code I am using:

$prev = get_adjacent_post(false, '', true);
$next = get_adjacent_post(false, '', false);

if($prev){
    $url = get_permalink($prev-ID);            
    echo 'a href="' . $url . '"Previous/a';
}

if($next) {
    $url = get_permalink($next-ID);            
    echo 'a href="' . $url . '"Next/a';
} 

As far as I understand, the parameters in the get_adjecent_post() function should consider all posts, since I am not restricting the selection to any taxonomy. However, it shows weird results. Currently I have 15 posts of this post type, the latest one only shows "previous" button (which is OK), but the second-latest only shows "next" button, as if there were only two posts. When I open another post manually I can go in both directions, but I am not able to go through all of the posts - as if there were some groups of posts created, and the get_adjecent_post() function only searches within these groups.

I am using Post Types Order plugin to customize the order of created posts and I think there could be some conflict.

Is something wrong in my code? Am I using the function in the wrong manner?