I experienced similar issues. It appears that in version 1.4 of Apache Commons Codec the Base64 function appends a CR-LF pair to the output. It did not do this in version 1.3 and was reverted to that original behavior in 1.5. (See https://issues.apache.org/jira/browse/CODEC-89 for detail.)
The current version (2.7) of spymemcached attempts to remove the last two characters of the Base64 output, assuming the 1.4 behavior. This will cause errors in the case where the provided Apache Commons Codec jar is not version 1.4.
I was able to work around the problem by either using version 1.4 of the Codec library rather than the newer version 1.5 or by modifying the spymemcached source to not strip the trailing two characters.
The spymemcached source should probably either be modified to work with the newest Apache Commons Codec or a separate, stable Base64 encoder should be used in its place.