No tuve problemas así jamás en el pasado. No sé si habrán cambiado las reglamentaciones de fan pages en Facebook.
Lo que me ha ocurrido es quizás intentar ponerle un nombre reservado. Esto quiere decir que a veces se reservan nombres especiales para empresas, personajes públicos y otras entidades. Por ejemplo, aunque no exista una página llamada "Donald Trump Reelection", quizás no te permitan utilizarlo debido a que lo mantienen reservado por si el equipo electoral de Trump quiere registrarlo. Twitter intentó hacerlo en una oportunidad debido a la cantidad de quejas que recibía por parte de empresas y personajes que no podían registrar sus nombres en la red social porque algún aprovechador utlizó el nombre primero y es así que durante un tiempo veíamos el "OK" al final del nombre de usuario.
Si no es este el caso y el cambio es demasiado drástico (ej.: "El Rincón del niño" cambia su nombre a "Super Modelos en Tanga de leopardo peleando en gelatina"), quizás no lo permitan tan fácilmente. Y cuidado con insistir. No sea cosa que te bloqueen la fan page o la cuenta.