Well, from book one, what we know so far:

1. When the Thiefmaker asks Locke his name, he takes a while to reply, thinking up something suitable. We learn later that Lamora was taken from a sausage vendor in the Catchfire district. Interestingly enough, his last name is the part that flows naturally to him. As to Locke, the book says he seems to ponder it deeply, then says he's called Locke, after his father.

2. When Locke whispers to Jean, he does so with five syllables. This was the part that made me wonder if there were small clues hidden in the books. Specifically mentioning that there were five syllables sort of hints at Lynch creating a puzzle for us, something we can try and solve. I'm probably crazy, but that's how I took it.

3. Jean reacts by saying that he'd have changed his name as well. I can only imagine that this might come into play, Jean being tortured at some point in the series so that the bondsmages can obtain Locke's real name. Although, in total disagreement with my idea about it being a puzzle, I wouldn't be too surprised if Locke had lied to Jean, too. He trusts Jean completely, but he knows the power of a name now.

Now, as to the five syllables. I'm guessing that's his full name, first and last. Assuming that his first name probably only has one or two syllables, like many names in the series (calo, galdo, jean, locke, etc.) his last name has either 3 or 4 syllables. A four syllable last name, in this series, would probably be somewhat ugly compared to Sanza or Tannen, etc. so I'm shooting for 4. We know he grew up in Catchfire, but we aren't absolutely sure he was born there. There could have been an unfortunate turn of events that landed his family in that particular district. We also know that at one point he told Jean he thought his father might have been a mercenary or a soldier. Whatever he was, he wasn't around, and mom didn't talk about him.

So, that's what I've got so far. It'll be interesting to see what the names look like in Carthain, and in Tal Verrar, since I don't really remember any names from that book. I'll be keeping my eyes out for last names, either way.