Passwords are not really crypted on Unix systems but hashed, i.e. they cannot be decrypted.
The hashing algorithm can be configured on Solaris from the traditional crypt_unix one to one compatible with Linux by modifying the CRYPT_DEFAULT parameter in the policy.conf file. For an example, see:
http://docs.sun.com/app/docs/doc/816...%2Fpolicy.conf
Of course, modifying this setting will only affect new passwords so you'll need to wait for all your users to have renewed their password to have a compatible /etc/shadow file. This might be never depending on your expiration policy.
This file is also telling what algorithms will be accepted while processing password. I don't know if such a configuration file exist in the Linux distribution you use but that would be another way to solve your problem.
Usually, this kind of heterogeneous authentication issues are better handled by separating the user's operating systems from the authentication service, usually NIS or LDAP.