Why does Time Machine hang/freeze on "Backing up..."?
I couldn't find any information on this issue, so I called Apple. After some digging, they told me that this could result from corruption in the OS X install. They asked me to reinstall OS X, which made me a little nervous, but when it was finished, I did a clean Time Machine backup and all went well.