Lo de la query es sencillo, usas regexp y ya esta.
He cambiado tu codigo y he creado la funcion buscar_letra();
<?php
include("conectar.php"); #Archivo que tiene la conexion de la DB
$letras = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; #Puedes poner las letras que quieras
$parte = str_split($letras);
$enlace = preg_replace("#(.*)#", "<a href=\"{$_SERVER['PHP_SELF']}?letra=\\1\">\\1</a>", $parte, 1);
echo $enlaces = implode(" - ", $enlace)."</br>";
$tabla = "usuarios"; #Nombre de la tabla en tu DB
$campo = "nombre"; #Nombre del campo a buscar
$pag = "perfil.php?usuario="; #Pagina a la que redigira con los resultados
if(in_array($_GET['letra'], $parte)) {
if(($dato = buscar_letra($_GET['letra'], $tabla, $campo, $msgerror))==0) echo $msgerror;
else {
$resultado = preg_replace("#(.*)#", "- <a href=\"{$pag}\\1\">\\1</a>", $dato, 1);
echo $resultados = implode("</br>\n", $resultado);
}
} else echo "Selecciona una letra para buscar usuarios que empiecen por esta";
function buscar_letra($_letra, $_tabla, $_campo, &$_error) {
$consulta = mysql_query("select * from `{$_tabla}` where `{$_campo}` regexp '^(".strtoupper($_letra)."|".strtolower($_letra).")(.*)$'");
if(!mysql_num_rows($consulta)) {
$_error = "No hay registros que empiecen por {$_letra} en {$_tabla}.{$_campo}";
return false;
} else {
while($leer = mysql_fetch_array($consulta)) $ret[] = $leer[$_campo];
return $ret;
}
}
?>
Gracias por el karma!