Last night, after still getting error 407, I hard-reset my phone. Update Profile and Update PRL then worked properly. I then restored from backup again, and again Update Profile and Update PRL would
not work. So clearly, the problem has nothing to do with outages. Apparently, something in the old phone's backup--probably in the registry--is inconsistent with the new phone's configuration.
My guess is that the phone's serial number gets copied into the registry; and then Update PRL and Update Profile foolishly use the registry's information instead of the phone's native information.
The bottom line here is that I had to hard-reset again, and reload all applications and tweaks from scratch.