Hay que diferenciar un índice de 3 campos y 3 indices de un campo. En el segundo caso, en tu consulta solo se va a usar uno de los índices.
Si vas a crear un índice con 3 campos, ten en cuenta el orden. Debe coincidir con el de la consulta.
Seguramente te vaya más lento porque no escoge bien el índice.
Puedes probar además de lo dicho anteriormente, algo así:
Código:
SELECT nombre,tomo,folio from publeje USE INDEX(nombre) where nombre like '$busqueda%' and (tomo is not NULL and folio is not NULL)
o
SELECT nombre,tomo,folio from publeje where nombre like '$busqueda%' HAVING (tomo is not NULL and folio is not NULL)