That could very well be a nameservice issue. Does the issue affect all users or just a small sub-set?
Are you able to login as root on the console? By default root over ssh is disabled, but if you've enabled it you can confirm whether the issue is nameservice or not by confirming that local users (files) login successfully and nameservice backed users do not.
What nameservices for users (password) are you using? Looking at your /etc/nsswitch.conf file will tell you the order in which users, passwords, groups, etc are looked up.
You're going to need to know a few details about your infrastructure so start by asking your colleagues for help.
* Identify the server make/model you have
* Many of the systems on the market today have System Processors (SPs), iLOMs, ALOMS, etc. These are small computers within the system that allow you to control the host remotely. Ask your colleagues for the IP address of this device. This assumes that it's actually configured, has an IP address, and is connected to your management LAN. If it is configured, ssh to this IP address using the administrators username/password. If it's not configured, then you'll need to be onsite with a laptop and a serial cable (DB9 or RJ45)
* Depending on the host you'll then be able to console on to the host. Typical commands will be "console" or "start /SP/console".
* Login as root
* Look at your /etc/nsswitch.conf file to see what order and type of nameservice you have to identify users, eg:
$ grep passwd /etc/nsswitch.conf
* If you have local users (see /etc/passwd) then try to ssh to this system and login using one of these users. If you don't have any local users, create one for testing purposes. See the man pages for groupadd(1M) and useradd(1M). Then try ssh'ing as that new user from your putty session. If that works you can now confirm that local users work and non-local users do not. This then pushes you on to the name service and you will then need to engage your Network Team or whichever group manages that service within your estate.
Can you login via the console?
Given how complicated this could get it's best you log a support ticket with Oracle and get assistance from the Solaris Network Team. It's going to require trussing 'sshd' and/or putting it in to debug mode, and snooping the connection to see where the problem is.
Check if root login has been enabled. In /etc/ssh/sshd_config there is a parameter "PermitRootLogin" if is set to "no" then change it to "yes" and restart ssh service # svcadm restart svc:/network/ssh:default