El problema estaba en la comparación, la función strcasecmp devuelve 0 si son iguales, -1 si es mayor el primer elemento y 1 si es mayor el segundo, por eso no estaba bien la comprobación que yo hacía.
Código PHP:
<?php
include ("connect.php");
$sql="SELECT DISTINCT categoria FROM categorias ORDER BY categoria";
$id_result=mysql_query($sql);
$letra_anterior = "";
while($row = mysql_fetch_array($id_result)) {
$letra_actual = substr($row['categoria'], 0, 1); // Metemos en una variable la primera letra de la palabra.
if ((strcasecmp($letra_anterior,$letra_actual) <> 0) || ($letra_anterior=="")) { // comparamos ambas letras
$letra_anterior = $letra_actual;
echo $letra_actual.'<br/>';
}
echo $row['categoria'].'<br/>';
}
?>