Solution 1:

Given that "upstairs" is a compound derived from the preposition up and the noun stairs, it seems most likely that it will act like a one-word prepositional phrase. For example, we can use the adverb right before it ("They are right upstairs"). Some linguists classify words that behave this way as prepositions (specifically, "intransitive prepositions"; for analyses and discussion, see Is "now" a "preposition"?).

If you accept that classification, then the use of "upstairs" as a predicative complement is not exceptional behavior. Prepositional phrases can clearly be predicative complements, as in the sentences "They are in the house" or "They are on the bus."

If you don't accept that classification, then I guess you do have to say that "adverbs of location" or whatever you call words like upstairs, downstairs, indoors, outside... (as well as "particles" like in, out, up) can be predicative complements.