Just for completeness, I'll update my findings in case anyone has this issue in the future and happens upon this thread.
Two things were contributing to my initial complaint...
1. TiBu DOES auto-sync its own setting to your sdcard, so after a wipe/flash it pulls the old Android ID from that save. As I mentioned in my first post, my sdcard died recently and had not yet been replaced which is why TiBu wasn't asking to restore my old Android ID. In TiBu under Preferences, there's an option to 'Auto-sync TB settings' which uses the sdcard. This is checked by default when you install TiBu and have an sdcard. When my sdcard died, this setting automatically unchecked itself. I found out you actually can re-check this setting without an sdcard and it will back up your Android ID somewhere, however you obviously have to re-check it manually.
2. Android 4.3 builds seem to have a common issue with restoring TiBu backups where the restore hangs at 0%. After I correct #1 above and restored my Android ID, TiBu was STILL hanging at 0% on restore. Looking around the web, it seems like there's a few different work-arounds. The one that worked for me was changing the backup folder location in TiBu to 'legacy' (TiBu > Backup folder location).
Two separate issues. Pretty confusing. Hopefully this can help someone down the road.