Custom Posts and Posts – next_post_link and previous_post_link not working together

You will need a filter on get_{$adjacent}_post_where to add your CPT.

function alter_adj_where_wpse_106694($where) {
  $where = str_replace("p.post_type="post"","p.post_type IN ('post','yourcpt')",$where);
  return $where;
}
add_filter('get_next_post_where', 'alter_adj_where_wpse_106694' );
add_filter('get_previous_post_where', 'alter_adj_where_wpse_106694' );

There is no flexibility to that callback. It is a simple string replace. If this is your site you should be OK, but if this is a plugin or a theme that you are distributing you need a much more complicated callback to try to compensate for the activity of other plugins and/or themes.