I use the exact same steps as you did.
After further experimentation, I discovered that photos can be moved from one album to another, as long as both albums were created, and photos were uploaded AFTER this new photo plugin was created (I think 1.7.0?)
So that would explain why yesterday, when I tried to move a photo from an old album created before 1.7.0, I was getting error. I looked back and the moves that were successful were photos that were very recently uploaded and album created AFTER 1.7.x
I did extensive testing, and my conclusions were
100% successful moves ONLY with photos uploaded and albums created AFTER 1.7.x
100% errors on moves attempted with photos/albums created BEFORE 1.7.x