This seemed to be an issue with relative paths. The mxd that I was trying to update was stored as Relative Paths in Document Properties. Once this was unchecked, the script worked as expected (without the delay).
So you can check each mxd manually, but given that this is a script, that slightly defeats the purpose. Unfortunately though ArcPy doesn't expose an API to change this particular setting (at least in 10.0).
So I have created a python script that uses ArcObjects to do it, with a lot of help from other people on the forum and outside. It needs an external library installed, but it is conceptually very simple. It can be found at http://gis.stackexchange.com/a/40666/217https://gis.stackexchange.com/a/40666/217
There may also have been an issue with long path names - if you are still having problems try copying to a local directory (I was on a network) and running the script from there. I found I then had to re-run the ArcObjects script to change the relative path setting, because mysteriously the ReplaceDataSource()
method turned this on in the copied MXD. This method has got really strange behaviour, and from what I've seen, it doesn't seem to be fixed in 10.1