Well, they are crazy! It makes a huge difference on most installs. They are just trying to cheap it up, I bet they are cheaper than other stores that actually do it right.
Most of the time the clay flue liner is cracked, therefore insulation is required to meet code. It's uncommon to see a flue that doesn't have a nice big crack going from top to bottom. Most uninsulated liners are dirtier than insulated liners. When I look down a flue I can usually see where the insulation stops a foot or so down. It'll be all dust up to that point, then it's black a flaky.
I don't think it's a must on all installs, uninsulated is better than no liner at all. If it doesn't fit, it doesn't fit. But if it does, why not? It's safer and more efficient. Just my 2 cents.