Vos me habias dicho:
   Cita:  
					Iniciado por pateketrueke 
  Entonces el str_replace() debes aplicarlo al momento de mostrar el dato, no al momento de agregarlo a la lista. 

     Entonces lo que hice fue ver la estructura del código que NSD me paso y intente adaptar el cambio en la ruta que el hizo que era lo que vos me sugeriste pero que yo no había entendido pq soy nuevo, entonces intente y consegui esto: 
- Funciona perfecto. Lo dejo acá, tal vez le sirva a alguien tb:
   Código PHP:
    <?php      
    $columns = 2;         
    $directorio = opendir("Categorias/Camp_Primera_Division");      
        # ponemos los valores en un array para poder ordenarlos   
        $ele = array();   
    while ($archivo = readdir($directorio))   
        {   
    if ($archivo != "." && $archivo != ".." && $archivo != "index.html" && substr($archivo, 0, 1) == "A")    
        {   
        $nombreArch = ucwords($archivo);   
        $ele[] = $nombreArch;              
        }   
        }   
    closedir($directorio);      
    asort ($ele);            
    echo "<table width=500px align='center'";      
    echo "border='0' cellpadding='3' cellspacing='3'>";            
    $z = 0;         
    foreach ($ele as $arc)      
        {      
    if ($z % $columns == 0)      
        {      
    echo "<tr>";      
        }      
    echo '<td><a href="'.$ruta.'Categorias/Camp_Primera_Division/'.$arc.'" target=_blank>'.str_replace("_", " ", $arc).'</a></td>';      
    $z++;      
       
    if ($z % $columns == 0)      
        {      
    echo "</tr>";      
        }      
        }             
echo '</table>';      
?>    
  - Quiero agracerles tanto a pateketrueke como a NSD, por su paciencia, dedicación y sobretodo por su tiempo. Es bueno ver que personas que saben mucho nos dan la posibilidad de aprender de ellos. Muchas Gracias !!