The story of prince Kshatrabandhu appears in the Vishnu Dharma. Vedantha Desikan not only mentions this in his Rahasya Traya Sara, but he also mentions this in his Tatparya Chandrika to Gita Bhashyam by Bhagavad Ramanuja. From what I understand from the Sanskrit text here, following the chanting of the name of God, he attained another human life, wherein, because of his constant remembrance of God's name, he repented greatly (tivra nirvedah) and then took refuge of the Lord (bhagavantham sharaNam upagamya) and then got liberated (hyamuchyatha). This answers all of your questions.
The important thing to note here is that he satisfied the condition "bhajathe maam ananya bhak", since that is the context in which this appears (a detail you missed in the question above). He did not chant the names of Govinda to rid himself of sins in his earlier birth. The chanting he performed was an end by itself. He did it because he liked doing it. It didn't hurt him. Because of this, it appears that Krishna's words of "kshipram bhavati dharmatma" came true. The chanting purified his heart to such a degree that it wiped out the sinful credits that could bestow not only a human next life but also a repentant heart predisposed to God consciousness, which made him take shelter of God and attain moksha. So, my dear Keshav, uttering your name for getting oneself rid of sins is not necessarily a pure purpose in doing so!! ;-)