Sorry.
There is a subtle bug in the crypto code in 1.5.7, sometimes giving this error.
I'm not really knowledgeable in crypto stuff, but the code was reviewed by a real expert in these things, and he could not see anything wrong either. So it remains unfixed, unfortunately.
Now, version 1.5.9 uses a different encryption / file format which should be more reliable.
It can read backups made by 1.5.7 but it will fail same as 1.5.7 sometimes.
When creating backups, 1.5.9 uses the new format.
So I'd recommend installing 1.5.9 on the old phone and making new backup there, to use the new format. But sounds like you already deleted your accounts on the old phone already... My apologies.