wubb, it sounds like doing it the quick way to delete a program deletes the title from the name list, though doesn't flag the space used by the program as usable space. Rebooting it via a power-cycle probably has it check that on power-up, then fix the issue in the startup process.
If it's any consolation, I occasionaly have to run a CHKDSK-like process on my Toshiba Tivo with the DVD-R when it has issues burning discs. Sometimes, if there isn't enough free space, or the free space isn't contiguous enough for the temp space needed while burning to DVD, I have to run this CHKDSK-like process on the Tivo. Works all the times I've tried it.