Hola,
Si revisas lo que pone en el manual de strtolower() (
www.php.net/strtolower), pone que depende del locale configurado. Para cambiar el locale puedes usar setlocale() (
www.php.net/setlocale). tendras que ponerlo a español (o castellano o lo que sea) para que te reconozca los acentos.
Y si no puedes cambiarlo, puedes usar las soluciones que dan los usuarios en los comentarios de strtolower().
Saludos.