Another update, just to help out anyone else that may be seeing this issue.

Seems the encrypted password supplied to me was not the right one. So if anyone else is seeing this error message then it is due to the encrypted password being wrong. Its worthwhile going back to sagepay and getting them to confirm all the details once again.

Ive had a new password issued by sagepay and all is now working.