No space to install would be the Phone Memory not the sdcard. It is a good idea to back your nandroids up on a computer to clear space though. I've had that issue myself quite a few times. Usually for me it has been certain roms causing me the issue, is it just titanium that won't install or are you unable to install anything from the market?
Retired: HTC Droid Incredible
Now Using: Toro