So I thought I'd solved this by clicking on each folder in the backup set and using the "relocate" option. To my mind the relocate option would do something like:
"Hey, that folder full of docs that you've uploaded to S3, well its moved to this new location locally, so just look in the new place for changes."
Instead it seems to go:
"OK, now that you've moved this folder from one place to another, I can't tell that the data is exactly the same, so I'm going to upload everything to S3 again."
My question is now whether this is a bug, expected behavior, or something that's due to be changed at some point.