O problema é que quando encontra a primeira ocorrência, você esta substituindo todos, depois vem a segunda ocorrência repetida e você manda substituir denovo, e entra numa reação em cadeia, bagunçando tudo...

Use a função `preg_replace_callback`:

    function MontarLink($texto)
    {
           if (!is_string ($texto))
               return $texto;
    
        $er = "/(https:\/\/(www\.|.*?\/)?|http:\/\/(www\.|.*?\/)?|www\.)([a-zA-Z0-9]+|_|-)+(\.(([0-9a-zA-Z]|-|_|\/|\?|=|&)+))+/i";
    	
    	$texto = preg_replace_callback($er, function($match){
    		$link = $match[0];
    		
    		//coloca o 'http://' caso o link não o possua
    		$link = (stristr($link, "http") === false) ? "http://" . $link : $link;
    		
    		//troca "&" por "&", tornando o link válido pela W3C
    		$link = str_replace ("&", "&", $link);
    		
    		return "<a href=\"" . strtolower($link) . "\" target=\"_blank\">". ((strlen($link) > 60) ? substr ($link, 0, 25). "...". substr ($link, -15) : $link) ."</a>";
    	},$texto); 
    
        return $texto;
    
    }
    
    echo MontarLink("ola mundo www.cade.com.br"); // ESSE FUNCIONA!!!
    echo "<br><br>";
    echo MontarLink("ola mundo www.cade.com.br outro site www.terra.com.br "); // ESSE FUNCIONA!!!
    echo "<br><br>";
    echo MontarLink("ola mundo www.cade.com.br mesmo site www.cade.com.br"); // ESSE FUNCIONA!!!