My solution is bit different from pcambra's. Actually I implement looking for previous and next node like this:
$pos = (int)nodequeue_get_subqueue_position($sqid, $node->nid);
$node_prev = nodequeue_load_nodes($sqid, FALSE, $pos - 2, 1);
$node_next = nodequeue_load_nodes($sqid, FALSE, $pos, 1);
Note: The previous is $pos-2, not $pos-1. The reason is that the returned position of nodequeue_get_subqueue_position is starting from 1, and the argument of position in nodequeue_load_nodes is from 0! The same reason for the next node.
Finally, the node you got is stored in the returned array. For example you can retrieve its nid like this:
$next_node_nid = $node_next->nid;