у меня
$ rpm -qf /etc/init.d/mysqld
MySQL-server-4.0.24-alt0.M24.1

и в нем 
# chkconfig: - 80 20  

из-за этого минуса вместо указанных runlevel после

chkconfig --list | grep mys
mysqld          0:выкл  1:выкл  2:выкл  3:выкл  4:выкл  5:выкл  6:выкл
chkconfig --add mysqld
chkconfig --list | grep mys
mysqld          0:выкл  1:выкл  2:выкл  3:выкл  4:выкл  5:выкл  6:выкл

ничего не происходит, остается выключенным. 
С остальными сервисами это работает.

например
# httpd          Start/Stop the Apache Web Server                               
#                                                                               
# chkconfig: 345 80 15  


chkconfig --list | grep http
httpd           0:выкл  1:выкл  2:выкл  3:вкл   4:вкл   5:вкл   6:выкл

думаю, вместо минуса надо указать, например, 345

И, кстати, непонятно почему при старте они оба 80?