Really? What kind of structure do their names have? I think even cultures that used full-sentence names tended to have some conventional ones.
And certain name ideas are very common cross-culturally, as witness Bogdan / Nathaniel / Theodore (and older Diodorus / Apollodorus / Herodotus / etc) / Dieudonné / Atallah...
Going to something I know better, Chinese names can be unique, and I know someone who tells me her father specifically attempted to ensure that nobody shared her name, but I wouldn't go as far as saying that being unique is the typical case. Some names (小丽, 国强) have an attractive meaning and are used with identical spelling by large numbers of people; other names (Xīnyuè, Sījiā) show a lot of spelling variation while always being pronounced identically.