"They are not a couple."
Translation:One nie są parą.
The construction here (a copular sentence) is "... jest/są + instrumental", for example "He is a worker = On jest pracownikiem (instrumental of pracownik)". Here, parą is the instrumental of para. Only accusative (direct object) changes to genitive when negated, other cases don't do that.
I guess it can, for example "He is a rich man" can be translated as "To bogaty człowiek" (although it's never the preferred Duolingo translation), so your variant can work here as well. Added now. Probably not many sentences here accept those, so trying them may mean you get failed a lot.