Does your system fail to shutdown? (ie: Hang?) If not, then it's definitely shutting down the process, just not in the way you might want. And was the startup script something you wrote, or came in a package? Is it correct to assume you've done some work with the /etc/init.d scripts? You're going to want to give us a bit more infomation.
Odds are, you need to have the process registered with chkconfig. Just putting Kscripts in /etc/rc#.d/ isn't sufficient, as I don't believe they get called if chkconfig doesn't know about them.
Essentially, your script needs lines at the top stating
# chkconfig: 345 99 10
# description: This is what my script does.
The first line states the runlevels this should be started on, as well as the priority startup and shutdown levels. (It would create S99 scripts in /etc/rc3.d, /etc/rc4.d, and /etc/rc5.d, and K10 scripts in all the rest)
On top of this, chkconfig will do a check in /var/lock/subsys/ to see if there's a lockfile out there for your service. So touch a file the same name as your service in that directory when it starts, and remove it when it quits.
Assuming you've got the above items in your script, it must be registered with chkconfig. In order to add a script, do
chkconfig --add <name>. Just make sure the script is in /etc/init.d/ with the proper name.