From what I've been able to read, the part of the NY liquor laws that the shop ran afoul of is the prohibition on liquor stores running a secondary business. The intent of the law is that liquor stores be licensed to sell exclusively alcoholic beverages. This prevents supermarkets from having a liquor aisle, for example. To this end, the statute and the regulators have designated certain items (such as corkscrews) that are OK for sale as accessories, but other items, and specifically in this case wine gift bags, have been explicitly prohibited. I haven't read the chapter and verse, but I suspect that the law leaves it up to the commission to decide what's acceptable and what's not. And they decided a while ago that wine gift bags are in the "not" category. I suppose because if you are going to require liquor stores to sell only liquor and a small set of accessories, you have to draw the line somewhere.
As the business owner himself admits, it's his responsibility to know what's in the regulations that go with his license, and to obey them.
It's too bad that US society can't make up its mind whether booze is a foodstuff or a vice.