I agree with Benjamin Kuykendall's answer. Certain kinds of noun phrases related to time or place can be used like prepositional phrases (the function played by prepositional phrases is often categorized as "adverbial", so you could also say "can be used adverbially") without a preposition. For example, we can say "I met someone nice that day": this sentence clearly contains the noun phrase "that day", with the determiner "that" and the noun "day". Without an added preposition, "that day" can be used as an adjunct of time in a sentence like this, taking the same function as the prepositional phrase "at the party" in your sentence.
There are various possible analyses of this: we could say that the noun phrase "that day" can be used directly with this function, or you could say that in sentences like these, the noun phrase "that day" is contained inside of a prepositional phrase or adverbial phrase that is somehow formed without the presence of any explicit preposition or adverb. But however you analyze it, it's clear that there are some pro-words that show the same kind of behavior as "that day". Temporal pro-words like this include today, tomorrow, yesterday. "Somewhere" is used for locative functions, as is "someplace". You could analyze "somewhere new" as a noun phrase or as some kind of prepositional phrase where "somewhere" acts as a preposition fused with a head noun. Although words like "where" are sometimes categorized as "adverbs", I think you have to treat the adjective "new" in "somewhere new" as modifying the pronominal element of "where".
Other related posts:
Another word that could be analyzed as combining adverbial and pronominal elements is "nothing": in a sentence like "They were up to nothing good," "nothing" functions to express both the indefinite object of the phrasal verb "up to" (a pronominal function), and the negation of the clause (an adverbial function). "Nothing" expresses in one word the same thing as the two separate words "not ... anything". A previous question about "nothing": On the Use of "nothing"
The question of whether the postpositive adjective construction involves an elided "that is" or "which/who is" is not related to the analysis of "somewhere". Some descriptions of postpositive adjective constructions in English refer to something called "whiz-deletion", which basically seems like your idea of an elided "that is". If this actually occurs, it would occur in many sentences, not just ones with "somewhere": e.g. "The plate left in the kitchen was my favorite" can be analyzed as the result of whiz-deletion of "The plate [that/which was] left in the kitchen was my favorite."