This is, indeed, one of the mysteries of the universe. I have myself spent 1..* lifetimes trying to decide how best to do this.
Enlightenment, they say, comes with ages and lasts for seconds ... but this is my take on the issue.
In collaboration diagrams we are concerned with conceptual level material. The implementation is not specified. That is, the act of creation of an object is left to (insert deity of choice here).
In sequence diagrams the issue becomes more germaine and a mechanism is provided to show the act of instantiation.
IOW, the collaboration diagram is only identifying
what information exchanges occur between objects, not how messaging flows (this includes instantiation). The sequencing of collaboration messages is there (IMO) only to link message chains together, not to imply some temporal information.
So to answer your question... I would not show the creational message just the method call. i.e. assume that the object is created.
Having said that....
I have a problem with this for nontrivial constructors. Example A: Zoo x = new Zoo(); which in itself creates rafts of other objects - cages, aquaurims, giraffes etc. In this case must the constructor call be shown? Probably not, given the above explanation.
Example B: Encyclopaedia EB = new Encyclopaedia (rafts and rafts of parameters); in this case there is a information component in the constructor call and I have for some reason decided that this information must be passed to the object exactly when it is constructed. That is, the parameterised information and the fact that the message must be implemented as a constructor is important. It would b nice to have this visuall represented in UML - but it aint!Hope that's gurulike enough for you (never answer a question without raising another

)
Bruce