Have you run an ACL Push Job against the server?
NSH access to a server is controlled by having Server.Read and Server.Browse permissions set in the CM GUI, and by what is set in your role's 'Agent ACLs' tab. All of this ends up in the 'users' file on the target server when you run the ACL push job.
The simplest way to resolve this issue is to delete the server and re-added. If this not an option; let me know.
When a user is created, they can work in two differing environments - The Configuration Mnaager (GUI) and the BL Command line (BLCLI).
At the time of creation, the user will be allocated to a number of Roles (for the GUI mode of work) and to a single-role (for the BLCLI mode of work).
So, when you type the command 'blid' you should see the user name and the BLCLI-allocated Role.
In order for the user to have access to a managed server, that server has to have its 'users' file contents updated. This is done when an ACL Push Job is run against that managed server.
So, in response to your question - You should A) validate the Role that the user has allocated to the BLCLI (N-Shell) mode of work and B) run a Push ACL Job against the server in question.