I have never seen a dyed BV, only other brands (ex. Choo) and it was always a disaster. You would have to remove the lining completely first. Then who knows what type of dye is best to cover what is already there? Even if you get lucky on your first try, you could not sell it as a regular BV I would definitely take indiaink's suggestion and look into cleaning it.