Yes, Vince. Simply check if rel=" is present, before replacing it:

function add_gallery_id_rel($link) {
	global $post;
	if (strpos($link, ' rel="') == false)
		return str_replace('<a href', '<a rel="gallery-'. $post->ID .'" href', $link);
	else
		return $link;
}