RESULT!
After struggling for a week to get a completed backup (and re-starting the process 3 times), TM is now backing up as it was before I upgraded to Mavericks - 670 GB took under 8 hours to backup to Time Capsule, and is currently backing up to USB at a reasonable rate (estimate has already dropped from 15 hours to 11 hours).
To summarise (I'm going to be a bit pedantic here, please bear with me):
1. Delete the file Macintosh HD/Library/Preferences/com.apple.TimeMachine.plist
Go to Finder, click Go, click Computer, click on Macintosh HD (or whatever your primary HD is called), click on Library, scroll down to Preferences, scroll down to com.apple.TimeMachine.plist, right click on the file and select Move to trash.
2. Rename your base station (Time Capsule) or backup HD.
To rename the base station, click on Spotlight (magnifying glass on top right of Apple menu bar) and type Airport Utility. In the Airport Utility window, click on the Time Capsule drive, and on the popup window click edit. In the window that opens, in the first tab (Base Station) click on the base station name and rename it (for example, I changed the name from Time Capsule Backup to Time Capsule Backup 1). Click update, and the base station resets. You do not have to change any other settings (e.g. internet, wireless).
To rename an internal or external drive, click on the name under the drive icon on the desktop, wait a second, then click again and the rounded "balloon" changes to a light blue rectangle. Type in the new name (for example, I changed the name from Backup to USB Backup).
3. Restart the Mac.
This is important!
4. Once the Mac has rebooted, open System Preferences (you can do this from Spotlight) and click on Time Machine. Click Select Disk and make sure you select the renamed disc from step 2. Click Use Disk, then click Replace "[Old Disk Name]". If you are using Time Capsule, you may have to type your wireless network password to connect to the disk.
5. Run the backup.
If you have previous backups on the disk, TM will recognise your Mac and will continue to use the existing backups. I you had previously wiped your backups, as I had, in an attempt to speed up the backup process under Mavericks, the backup should now proceed as normal (about 70-90 GB/hour).