I have two liens from the state on my credit and I dont know if it is the same but I was advised to contact the tax department and get a letter stating my release of lien.  Then I had to go to the clerk of courts where they gave me a letter to have it removed from the credit bureaus.  As of today I still have to mail those documents off to the bureaus so that it can be updated.  It may be a bit easier than we think depending on where you live.