While harsh, I have had great luck with some cheaper leather cleaner. It is an Eagle One product and I believe it is just called "Leather Cleaner." I cleaned up a car for sale that had years of smoke and other stains on it and the Eagle One stuff worked where others would not. One the leather on leather stains, a good amount of buffing was required. Also, the cleaner will dry the seats out so be sure to condition after using it.
-GT