In EA 6.5, when adding message between objects in Communication Diagram, an association link should be created firstly, then message can be added to the link. "The association link" is confusing with "association concept" in Class diagram. I think it is better to replace the association icon with a new message icon into Communication Toolbox since it has different appearance from which in Sequence Diagram. 
The
[size=13]UML 2.1 Superstructure (interim)[/size] Specification in
Table 14.4 Graphic paths included in communication diagrams notes that the only edges to be shown on a communication diagram are Messages.
The EA help file says:
Communication messages in Enterprise Architect are always associated with an association link between object instances. Always create the association link first - then add messages to the link. and this is YaKun's experience.
However the issue is exacerbated by EA's UI (
Unique Interface). The Quick Linker uses the terms
Link and the Toolbox uses the term
Associate. A Link is really an
instance of Association (used to join two
instances of Classes). It may be better if EA standardized on Link (as shorthand for Association Link) and when the properties dialog the the link you've just created was captioned
Link Properties rather than
Association Properties.
Just why a message has to be associated with a Link is not clear to me, and certainly not implied by the UML specification (as I read it). However, be that as it may, It is disconcerting to right click in the message just associated and find the menu item
Collaboration Properties... then, when I select it, the dialog is captioned
Message Properties.
Now it seems fairly clear from the behaviour of the message "thing" and the
Diagram|Set Visible Relations... [Ctrl+Shift+I] that there are two relations in play here - so again, why the requirement for the Link?
Oh, by the way, the message edges on the communication diagram
never have arrow heads. So they should be marked
Direction: UnspecifiedConsistency, Consistency, Consistency! TMPaolo