A user was not appearing in User Contacts on an Avaya Phone System. This is like a global address list of all phones.
There is actually a Ex Directory tick box that can be turned on for this to happen under the Users/ User Tab make sure this is removed