There is a common trope in fiction: when a character find themselves in a dark place out of this reality (somewhere in the eldritch realms, dreamscapes, lost cities of Carcosa or R'lyeh, etc), at first they do not fully understand their dire situation thinking that they are simply in a strange and unfamiliar location on Earth. Eventually they look up to the night sky and see that the stars are wrong in this place, so it cannot be anywhere in our universe.
I am trying to incorporate this trope in my story. A modern citizen got lost beyond space and time. They suddenly find themselves in nighty wilderness under the starry sky (the moon or any other celestial bodies are not visible). At first sight everything seems at least familiar, but... Then, they notice something eerie with the stars above, so they realize that they are likely not even anywhere in our reality.
What can possibly be wrong with the stars in the night sky?
There should be something with the stars themselves (brightness, colour, luminosity), their positions or relative movement, that is visible with the naked eye and that is commonly and widely known not to be present in our world. Also, I would like the answer not to be too difficult to imagine/visualize and to sound a bit lovecraftian-style scary.
I personally came with the idea that every time the person looks up to the sky, the constellations are entirely different, but for me it seems a bit too straightforward and silly.
Assume the person in the story is somewhat clever and observant, yet has no special education related to astronomy, stellar mechanics or something, neither they have much experience in spotting constellations.
PS: Bonus points for a subtle and uncanny feature that allows for more gradual realization, but something that is obviously wrong is OK, too.
Some updates based on the comments:
UPD1: Strict scientific accuracy is not required, I don't mind moderate handwaving for the sake of storytelling. Yet, I don't want the solution sound entirely magical.
UPD2: The lights visible in the sky may not neccesarily be actual stars. I'd like them to be some stellar/atmospheric phenomena, though.
Brainstorming should produce the most horrific moment, from almost familiar to absolutely eldritch horror in shortest amount of time. Preferably without talking the eyes of the constellation while stumbling around.