Se trata de un bug de ciertas versiones o aparecido entre las versiones 5.1.50 y 5.1.51, producto de intentar prevenir borrados en cascada recursivos y/o circulares.
Ese bug ya está informado en
bugs.mysql.com desde el 5 de octubre (hay que googlear sin miedo, estas cosas suelen aparecer fácilmente).
El problema se produce no tanto por la cantidad de registros base a modificar, sino por los registros que dependan de cada uno de los de la base. En tu caso al menos un registro de la tabla que modificas está relacionado con más de 250 registros de otras tablas y por eso salta el error.
Tienes dos opciones:
1) Buscar, descargar e instalar la versión de MySQL Server 5.1.50.
2) Descargar la versión de MySQL Server 5.1.52, que fue liberada el 1/11/2010