I ride a train from upstate New York to NYC daily. The ride is about 90 minutes each way. I've had the idea pop into my head during that boring ride that I could sharpen my SAK - you know, do something somewhat useful to pass the time. But my smarter self always says, "No, scro! That will end in tears." No matter how innocent my intention, in that setting it would just be seen as a threatening thing to do.
In the OP's case, I see something similar going on. I reckon there aren't too many spots on the floor of the average Costco where a customer pulling out a knife (even a very small one) wouldn't attract negative attention. It is about context. Sure, the employees may have boxcutters in their pockets. They have a job to do. They are known to the other employees. There is comfort and familiarity there that allows the use of a boxcutter to fit neatly within that context. A customer, on the other hand, is an unknown and a knife in his/her hand would be out of place - a threat.
You also have to keep in mind that the train I ride every day and the Costco you go to are private property. I am not a lawyer but I am pretty sure that once I step into either place, I relinquish certain rights or aspects of my rights in exchange for being able to use their services. That includes removal from the premises if I act in a way that is perceived as threatening. Both are "public places" as in "lots of people", but it isn't public property. The idea of one's rights are then in question. Just like if someone came to your house. You expect them to follow your rules, their rights are secondary.
I hardly think anything threatening was going on and it sounds as if the whole thing was blown out of proportion by the Costco employee. However, it is a simple sad fact that the setting in which one chooses to fiddle with a knife of any sort for any reason matters. In some cases, exercising discretion is more important than exercising one's rights. On the other hand, you may not have the rights you think you have depending on where you are.