How to deal with the "Payment failed at the payment server" error?
I had a similar problem with the token conversion, be sure you're using the -dev version (2014-May-23 or later) of Commerce Sagepay before trying anything else. 

Note: probably related to: https://drupal.org/node/2115203