Depends on your definition of 'name' and your system/formalization of the act of reference and/or semantics.
In this case, 'name' seems to mean 'proper name', and there are systems explaining proper names as symbols used to refer, but not to carry semantic charge (whatever that would entail). For example in my native tongue many town names are named after rivers large and small that do - or - only used to flow next to / past those towns. Yet we don't suddenly change the proper name: the reference still works, but we do not need to cognize the semantic contents (originally associated with the name, if that was the case anyway; if you know where Baroomghtown is, I can use the term to refer to it and my reference will succeed as it were).
That was a mouthful. My (insignificant) point: perhaps they would only need cognitive machinery for referring to (in some simple(?) sense) / distinguishing between themselves. That is: (1) usage of proper names does not (necessarily) imply ability to speak a language (perhaps that's all I meant; talk about nitpicking..); (2) there's quite a lot of research showing that animals form concepts left and right (could dig something up, but googling under those keywords would yield enough). Consider this interesting report:
Under Pepperberg’s patient tutelage, Alex [a parrot] learned how to use his vocal tract to imitate almost one hundred English words, including the sounds for all of these foods, although he calls an apple a “banerry.”
“Apples taste a little bit like bananas to him, and they look a little bit like cherries, so Alex made up that word for them,” Pepperberg said.
(NGM, 2008:
http://ngm.nationalgeographic.com/print/2008/03/animal-minds... (a curious article))
So it might be possible to conceive of a schema such that [arbitrary symbols (sequences of syllables, etc.)] + [concepts] => proper names; and those would indeed be what we are used to calling 'proper names', a subset of the category denoted by 'names', not something else.
However, I agree completely with the sentiments re: fears of (over-)anthropomorphizing and projecting our own 'theories of mind' onto other life.