Problemas con la letra Ñ

[harvey]

Tengo un código que crea un indice con las letras por las que empiezan una lista de resultados (nombres) de manera que si, por ejemplo, hay apellidos que empiezan por la B aparece la letra para pinchar y ver esos nombres pero si no hay ninguno, omite poner la letra. El resultado es una linea así:

A - B - D - E - F - G - M - N - P - R - S - V

El problema lo tengo con la letra Ñ. Para saber cual es la primera letra del resultado, en el código uso substr ($row["apellido1"],0,1) pero esto con la Ñ no funciona. Para que funcione tengo que comparar los dos primeros digitos, en vez del primero solo. Modifiqué el código para que me incluyera la Ñ (con un If) pero aún asi la busqueda de de resultados que empiecen por Ñ me da los mismos resultados que empiezan por N también.

Los documentos los he actualizado estos dias a utf8, así como la base de datos y la conección a la misma.

¿Alguna idea?