Why is getting a chimney sleeved such a hassle ... and expensive
Just for a little perspective, I have a ~100 year old chimney (no fireplace, just a vent for the gas appliances in the basement).  There was no sleeve and no chimney cap when I bought the house.  

Recently, I had someone come out to fix everything before I had the roof done.  He removed the existing cap along with all the exposed brick, rebuilt the whole exterior chimney, installed a ~30 foot liner, installed the new chimney cap, and hooked up all the vents in the basement.

All of that ran $800 (in Chicago).

Given that, the $2000 estimate does not sound out of hand (considering the 45' height)... but ranging up to $15000 seems suspicious.  Perhaps someone will have a little more insight on why there is such a wide range.