I wasn't finding where TiBu was keeping my backups after a wipe, so I assumed it was getting stuck on the phone's memory and wiped. Guess I should have RTFM
From the Titanium Backup manual
i. How to restore your backups after installing a ROM (if you wiped your phone)
If you just formatted your SD card, don’t forget to copy the “TitaniumBackup” folder (and possibly your license) back from your PC.
Download Titanium Backup from Market
If you intend to restore system data (eg: MMS/SMS) from a different phone/ROM, enable the “System data migration” option now.
Click the Backup/Restore tab
Click Menu (the button), Batch
Click “Restore all missing apps + system data
Reboot your phone
It’s done ! The only thing you may have to adjust is usually your wallpaper/widgets.