have you changed the nut? Even the best tuners in the world need a good nut. Gibson install plastic nuts on all their guitars (except the custom shop ones). 20 dollars will get you a pre-cut self lubricating tusq nut which is cut to size for your gibson. All you need to do is sand the back until you are happy with the height. Swapping nuts is a pretty simple job and will increase your speed of tuning and tuning stability immensely. Try that before springing for new tuners. If you are not confident in doing it yourself, then get a tech to install one.
ON the locking tuner front: they dont increase tuning stability, they just make string changing faster because you dont need to wrap them round the posts very much. I have sperzels on my strat.
If you have replaced the nut and you still feel the need for new tuners, then have a look at grover rotomatics. Nice and chunky all metal affairs that will still maintian the gibson vibe. The rounded corners on the tuning keys are really comfy when restringing too.