So, I did a full backup, and gave it a password...
Upon successful rooting, when trying to restore, it almost immediately says "completed" and never actually restores. I'm quite certain that I've got the password correct, and my phone never had a file-system encryption password set, so I left that blank.
Am I just hosed? The file on my PC is about 400 megs...
EDIT: HAH! Even though I didn't have a desktop backup password set when I created the backup, setting one, and using it during the restore seems to have solved the problem!