Pages with attachments almost always fail to move to a different space

When trying to move a page with attachments, or a page that has children which have attachments, I will get "Move failed. There was a problem contacting the server."

At first glance, this might sound similar to other bug reports about this issue, but the difference here is that I never lose any attachments or otherwise end up with missing data. The pages that didn't move are still where they started, and have all of their attachments.

When hitting one of these pages that won't move, I've experimented with moving only one of its children that doesn't have attachments and that always works.

Here's the strange part. I was able to move one page with a child that had 26 attachments to a new space. All of the attachments made it with the page to the new space just fine. However, the page itself had links to these attachments embedded in the page code (they were PDFs). All of the links had "oldspace:" inserted in front of the links, so they were all broken. I edited the page removing the "oldspace:" and the links worked once again.

I tried rebuilding the ancestor table, but that did not change anything.