This should only happen if the key is not a valid user. keychain add does do basic checking for UUID validity and can reject keys if they're the wrong length, as presumably the most likely issue should be copying and pasting keys; I'll do some testing this weekend.

Alternatively, SL may throttle display name lookups; see llRequestDisplayName() documentation.