A prescriptivist pedant might insist that this is incorrect, and they should instead say "I need to go to a store", but in my judgment as a native speaker, the version with "the" is more idiomatic, and the version with "a" sounds stilted.
To repeat another part of my initial post, it's like the use of "the" in "the bigger they are, the harder they fall". It's clearly a different usage/meaning/sense of "the" -- in fact, most other languages use a different word for that sense. (German uses je ... desto.) It would be very dubious to explain all uses of "the" as "oh its when the noun has definiteness". It wouldn't cover that case, and it wouldn't cover (the typical use of) "I went to the store".
Some of the statements (by other people) in this conversation are wrong, based on applying a school-style oversimplified explanation that doesn't really match English usage.