In general, all affected parties have a choice of appealing a decision made by a court. From linked article:
If, as expected, the PPP and its partners decide not to challenge the court’s judgment, they will have to build a consensus around a new PM. (Emphasis Mine)
There are always other options available to legislature. They can pass a law which retrospectively changes the legality of the court's decision. (i.e. If Gilani was convicted of crime X, and court says this means he cannot be Prime Minister, the government can pass a legislation that allows even persons convicted of crime X to be a PM.) One particularly famous example of this happened in India in 2006, when several Members of Parliament were forced to resign (and some were disqualified) because of a law barring them from holding an "office of profit". The government brought in an act to change the law, that too retrospectively from 1959 onwards, so that the disqualifications were invalidated. See this and this.
More extreme measures are also possible, like declaration of emergency, etc.
This requires some definition of terms. In some ways, the Court is part of the government. However, more clearer terms to be used are Legislature, Executive and Judiciary. These are the three branches which provide the Separation of Power in the Commonwealth systems. The legislature are the state and national assemblies, which make the law. The executive is the branch that implements the law. The Judiciary is the branch that monitors and arbitrates the implementation of the law. In your question, the term government roughly translates to the Executive (i.e the PM, Ministers, bureaucrats etc.) When the Judiciary makes a decision, it has the weight of a law, and none of the three branches can operate in opposition to the law. Thus legally, all court decisions have to be followed. Since the PM is not following a court decision, he is acting illegally and can face action because of it. In this case, the Supreme Court has chosen to decide that it can remove a PM from office for contempt of court. Whether it has the power to do so, I do not know.