I've been through that several times but getting to the Market didn't seem to take unusually long. What bothered me was running Titanium Backup Free version and having to answer "yes" to all the installation permission questions. This morning I ponied up the $5 to upgrade to the paid version, which offers the ability to do it all at once. I figured with all the messing around I have been doing on my phone it was worth paying for it.
It would be nice to have Titanium saved to the SD card and not have to re-download it each time but I guess it doesn't work that way.