There are a variety of different reasons why you might not be able to add a user to your account. I do apologize for the lack of detail included in these error messages, but we will likely not be able to do anything for these folks with these @handles at the moment.
We are actively working on improving the processes and information delivered related to this feature, but in the meantime, I think the best thing you could do is have these users create a new @handle and add those handles to your org account.
I know this is not ideal, but please do know that we are working hard to improve this situation.