/etc/init.d/mysql is part of the package mysql-server-5.1. You only have mysql-server-core-5.1 installed, so I suspect the script remains from a removed, but not purged package.
mysql-server-5.1 is correctly depending on mysql-client-5.1, but mysql-server-core-5.1 is not. I think the proper way to fix this is not only let the init script check for the presence of mysqld, but also for mysqladmin. -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org