De entrada definir un indice (no unico) sobre el campo fecha y luego creo que sera mas rapida esta que la tuya
SELECT DISTINCT fecha FROM usuarios ORDER BY fecha;
Si no es suficientemente rápida
Cita: La cláusula FROM table_references indica la tabla desde la que recibir registros. Si nombra más de una tabla, está realizando un join, Para información sobre la sintaxis de join, consulte Sección 13.2.7.1, “Sintaxis de JOIN”. Para cada tabla especificada, puede opcionalmente especificar un alias.
tbl_name [[AS] alias]
[[USE INDEX (key_list)]
| [IGNORE INDEX (key_list)]
| [FORCE INDEX (key_list)]]
El uso de USE INDEX, IGNORE INDEX, FORCE INDEX para dar al optimizador pistas acerca de cómo escoger los indices se describe en Sección
13.2.7.1, “Sintaxis de JOIN”.
En MySQL 5.0, puede usar SET max_seeks_for_key=value como alternativa para forzar a MySQL a que realice escaneos de claves en lugar de escaneos de tabla.
12.2.8.2. Index Hint Syntax
SELECT DISTINCT fecha FROM usuarios USE INDEX (nombre_indice_fecha) ORDER BY fecha
Creo que obtendrás una mejora que te va a sorprender...