Just what the title states. It stems from observation & personal experience that a person/dog/cat/monkey is more likely to relieve oneself immediately after it wakes up from the peak-sleep cycle of it's body-clock. Is this observation true? What causes this behaviour ?
I think we can actually go farther than mere behavioral argumentation. The separation of the autonomous nervous system into parasympathetic and sympathetic is, one the one hand, associated with the sleep/wake cycle, on the other with parasympathetic/sympathetic activity (low/high epinephrine secretion). This duality certainly applies to all vertebrata (i.e. big animals), as fight & flight is associated with all vertebrata, see e.g.
In other words: from the existence of fight or flight in all vertebrata I infer the existence of a dual autonomous nervous system (parasympathetic and sympathetic) in all vertebrata, although there may be other proof. Since in sleep the parasym. NS is active, the bowel moves. Conclusion: the bowel moves in the sleep of all vertebrata.
I'm prefixing this one by saying that I don't actually agree with you (also, I think the old nut that the plural of "anecdote" is not "data").
That having been said: wouldn't the simplest explanation just be "because it was likely a long time since the animal's last 'relief'" since it's been sleeping for XXX hours? Or would you argue that this observation is also true after, say, a 20 minute nap?
Also, what does this have to do with a nervous system?
Digestion is an energy consuming process. It is, therefore, often followed by a period of rest. Animals will, consequently, often digest during sleep. It follows that they will eliminate the waste products of digestion upon awakening.
Given the above, I doubt there is a causal link between sleep or rest and the need to commune with nature, water a tree, appease the porcelain god, or whatever your preferred euphemism happens to be, soon after awakening.