Well, I think part of the issue here is that we tend to muddle up a great many different issues here due to the ambiguity of the term 'religion'. After all, if the government is not supposed to endorse religion, this can't be interpreted as saying that the government is not to endorse anything that anyone thinks vaguely religious in some sense or other -- there's probably nothing that wouldn't be ruled out by such a standard, since for a lot of people 'religion' is an extremely wide net indeed. So there needs to be a criterion of what counts as 'religion' (1) that is objective, i.e., not simply arbitrary; (2) that is not itself question-begging; and (3) that is definite and restricted enough to allow one to enforce non-endorsement practically. This is not a simple thing to find.
Why, for instance, should one consider a statement about God to be religion in the relevant sense? Obviously it's religious in the vague sense that some people appeal to God in religious contexts; but people appeal to a lot of things in religious contexts. Suppose, for instance, that it is a widely held belief in our society -- as in fact it is, although by no means universally held -- that the existence of God and some sort of moral providence whereby virtue is in the long run rewarded and vice in the long run punished is simply a fact of the universe. On such a view, it is something relevant to good governance; is the government to recognize no facts that might be considered in some sense 'religious' facts? In which case, how is it supposed to determine which facts are the 'religious' ones? Or is it supposed to apply some independent standard of factuality to determine that, regardless of the widespread view, it is not a fact at all and can be dismissed because of that (as the Explicit Atheist suggests)? In which case, how is this not, in fact, meddling in religious matters already by governing on principles dismissive of any religious views that have as part of their make-up a belief in the existence of God and divine providence? And what if the independent standard were to say that it was (at least plausibly) a genuine fact (or, to put it in other terms: how is one to formulate such a standard in a way that it would consistently rule out talk about God)? And if we know it won't, we can only do so because we know the standard -- and then it's reasonable to ask what it is.
Consider a similar scenario. There are a great many people in our society who classify morality as essentially a religious matter; and it is certainly true that religions are built as much around alleged moral values as they are around alleged higher beings. There are also some who don't classify morality in that way, and consider appeal to moral values like justice to be nonreligious (and a small minority who regard it as fundamentally, even if not obviously, inconsistent with what they would tend to classify as religious). If it's merely a matter of how people in the society are classifying it, whose side should the government take in determining whether it can appeal to moral values? On what objective basis could such a thing be decided? But if whether or not appeal to moral values is religious is something independent of the views of people in society, in virtue of what principle does government decide such a matter, and on what authority does it appeal to that principle regardless of the views of the citizenry? And if appeal to moral values is legitimate, what, precisely, makes appeal to moral providence illegitimate?
The obvious reason why one should reject the sort of government action you mention in your hypothetical scenario has nothing to do with religion as such; it's simply that a lot of people would oppose it, vociferously and actively, and in a government that at least purports to be based on the people that's not a minor thing. It's also clear that this ground will clearly allow cases like 'In God We Trust' as legitimate, as long as there is not a sufficient groundswell against them. So there would have to be something particularly religious to rule it out. Now, one can work out a concept of religion by doing what in fact we have done: start with paradigmatic cases like religious tests, of the sort put forward in the Test Act, and established churches, of the sort found when we first began, and work out from there by analogy. But analogy always runs into the problem that it becomes more and more attenuated, and reaches into more and more gray areas, and eventually, if taken too far, extends into everything. So we would need some more principled line; and that requires a well-grounded notion of what constitutes religion in the first place. Anyone who thinks the motto is illegitimate endorsement of religion, for instance, owes us a basis on which to think this view should take precedence over views in which it is not, because it is not (in the relevant sense) religious at all, or because it is not (again, in the relevant sense) an endorsement at all. And this is because everyone in the discussion owes everyone else a similar account of what is and what is not relevant. And no one so far, at least as far as I can see, has an account that would be generally accepted.
UPDATE: Nathanael has an excellent post on the more serious danger here of making the nation a sort of ultimate object of worship. I'm reminded of Mit brennender Sorge:
Whoever exalts race, or the people, or the State, or a particular form of State, or the depositories of power, or any other fundamental value of the human community - however necessary and honorable be their function in worldly things - whoever raises these notions above their standard value and divinizes them to an idolatrous level, distorts and perverts an order of the world planned and created by God; he is far from the true faith in God and from the concept of life which that faith upholds.
And the worry is that, while this might well not be a divinization of the people or the state in the way that Nazism (which the encyclical has in its sights) is; but there are a thousand ways to skin a cat, and there is a legitimate worry that this just might be another, more subtle, way to do it.
