It works both ways in this sentence: "Ei au un guvern nou."
However, it is not always the case. The inversion is acceptable only for some adjectives. Another example would be "Ei au ținut un minunat discurs / un discurs minunat." (= They gave a wonderful speech.).
You have to keep in mind that if you want to put the adjective first, you also have to give it an (indefinite/definite) article, e.g. "un nou guvern / noul guvern".
Also, the adjective often comes before the noun in literary works. For example, "o preafrumoasă fată" (= an overly beautiful girl), from Mihai Eminescu's poem "Luceafărul".
I see, it looks like romance languages like to do that, right? hahaha I'm kidding. Today I was talking to a romanian friend and I said "I'm running with my last homework" and he translated as "fug cu ultima temă". I guess ultimul and primul are adjectives to be in this list, am I right?
Thank your so much for the detailed information! :)
True, ultimul & primul are placed before the noun, but keep in mind they're not adjectives per se. They're called ordinal numerals with adjective value :) They can also have noun value when they don't determine a noun (e.g. Ultimul merge pe stradă. -- The last one is walking on the street).
Such numerals can also be placed after the noun (e.g. "a treia mașină" or "mașina a treia" -- the third car). However, ultimul & primul already have a definite article (-ul) so they need to come before.