En la linea que genras el link podrias cambiar el uso de la funcion urlencode() por
rawurlencode()... Asi los espacios no serán convertidos en +:
Código PHP:
echo '<img src="'.$iconos[$clave].'.png"> <a href="'.$dir.rawurlencode($valor).'">'.$valor.'</a> ';
Sobre el uso de mayusculas al inicio del nombre... Es raro, deberia funcionar igual... Buscare haber si encuentro algo
Un saludo,