Is it possible to determine an observer's position on Earth from a photo of the night sky and the time of the shot? To my knowledge, this question can be related to celestial navigation on one hand and to attitude (or orientation) determination from stars direction on the other hand. However the combination of this two methods does not solve the problem, so I am wondering if there is a different approach.

In celestial navigation, the altitude of the stars (elevation wrt to the horizon) at a given time can be used to determine the observer's position. The limit of this method is that the horizon must be visible, which is not necessarly the case in a photo of the night sky.

An image of the night sky can also provide information about the attitude (orientation) of the camera wrt to an inertial frame. The measured direction of a few stars (from their position on the image) and their known direction in an inertial frame give an estimate of the attitude. This method is used in devices called star trackers onboard satellites for instance.

The combination of this 2 approaches fails to solve the problem because the information about the horizon is still missing. Indeed, the orientation is found with respect to the inertial frame, not the local frame, and thus the horizon is still unknown.
What can you tell from a picture of some stars?

At the very least, you need a recognisable asterism

If the exposure is too low or the light pollution too high to identify unambiguously an asterism of three or more stars, you're simply not going to be able to tell much from the photo.

An asterism on its own can only tell you where the picture wasn't shot.

If a star in a picture has a declination of $60^o$, you can rule out all shooting locations south of $-30^o$ latitude. A star like Polaris can only really be seen in the northern hemisphere, while Sirius can be seen everywhere south of Svalbard.

An asterism plus the horizon is sufficient for determining latitude

If the edge of land in the picture is sufficiently close to being the actual horizon (and not a range of mountains) and it is present alongside a recognisable asterism in the photo, you can calculate the latitude. This is true for any magnification, as you can use the angular distance between stars (a known quantity) to measure the angle to the horizon. I can't think of any special locations where you wouldn't be able to determine the latitude from the stars + horizon.

I haven't really done the math for how accurately one would be able to determine the latitude, but here are some considerations: There are two sources of error, the position of the stars and the position of the horizon. The star image may spread out over several pixels, and if the picture was shot through a standard camera and not a telescope, there would be an error, at a wild guess, of around ten arcminutes. The horizon can appear lower than $0^o$ depending on your distance above ground, but the effect is small. Looking out from Mt Everest, the horizon will appear a twentieth of a degree lower down than it ought to. I believe the horizon's exact position can also be obscured through atmospheric refraction.

All in all, the error in the angle between an identified star and the horizon equals the error in latitude of your identified position. For a 10 arcminute error, that corresponds to ten arcminutes of latitude, which is about 18 kilometres. 

For longitude, you need global, not local time

If you only have local time, the photo could have been taken anywhere along that latitude. If you have some form of global time (UTC, GMT, whatever, it doesn't matter which as long as you know what it is) you can figure out longitude from there.