Unfortunately that isn't true. Businesses have a right to refuse service for a wide variety of reasons. Like you said though those protected classes are illegal to discriminate against.
That is why you can have rules, like "no shirt no shoes no service". So in this case it is if you bring a gun you will be asked to leave.
Although now if that store was ever a victim of a robbery I would bet the response time is very slow....