There are really lots of possibilities.

Let's get some more info. What model TiVo is it? Have you ever changed the hard drive? How does it connect to TiVo?

Had a Similar Issue

We noticed that if you restart the recorder, it seems to be OK for a couple of weeks (this is with a fairly new HDD). What "fixes" it for us is completely dleting everything in the "Recently Deleted" folder. Yes, a long manual process. We are using a Tivo Series II (HD XL) with 2 TB. When the recently deleted gets between 350-500 entries is when we see the problem. We have NEVER seen this Tivo automatically delete ANYTHING to make more room.

So what error do you get if/when it fills up completely?

my tivo is doing the very same thing. It is a series 3 and i did replace the hard drive recently. It seems like it only started doing this when i cut cable and started using over the air channels. It connects just fine every night and says everything is ok, yet the program guide says " to be announced" and i get a message that says program data is running low.

This is a series 3 on cox cable. It's on my home network, always says sucessful and did work fine for years. I also have a series 2 on the same network and it hasn't had a problem in 12 years. I've been going over this with the idiots at tivo who keep saying they haven't heard of the issue. Per tivo, I've done all the kikstarts, reset the directory, zip code, deleting thumbs, and all sorts of other stuff. They finally said it had to be turned in for a new one which means I pay, of course. This one is already a turn in from my new one that went out just after the warranty period. Then with this one the power supply went out in a year. I also put in a 2gig drive from WN when I git the power supply from them. This has to be a software issue and it's a real shame tivo has such poor customer service. As others state, reboot makes the message go away but only for a few days. In addition to the message on the screen, I get a message notice on it (like you get when there's a lineup change) the day before.
I haven't tried deleting the deleted files so I'll give that a try and reboot. I hope I can find a way to do something better than delete one at a time - anyone know how?

Sounds like it's just a hard drive problem to me - the hard drive can't store the data that's being downloaded.

Have you tried a kickstart 57 with the overnight test? What were the results?

==============
Yes, I tried all the kickstarts. The drive tests were all "sucessful"
The message used to clear on a reboot but now I'm getting the SO3 error and on reboot it still has the program data message but it increased by 3 more days over what it said before the boot. I did delete all the deleted files before the reboot.
Anything else to try?

What is the exact version of your OS from your System Information screen? Please post the whole long string.

I'll post it tomorrow, doing another 57 right now.
I got the S03 error, unplugged the network for three days, restarted and it connected but instead of saying "sucessfull" it said "pending restart". Restarted and it said "sucessful" but there's alot of missing data, the running out message still appears and a formal TIVO message came saying Sunday was it.
I'm going to run guided setup tonight and if that doesn't clear it, I'll replace the hard drive tomorrow.

Software is: 11.0m-01-2-652
Got the green screen on the 57 but the TIVO was all fired up and running only a few minutes later - data still missing, not on all but quite a few channels

This is getting crazy. I put in another hard drive that I know is good and it's still not loading the data and only showing it until the same date, tomorrow, that the message was citing with the previous hard drive. I'm not a super electronics guy but I thought all this sort of stuff was hard drive related. What other kind of component can be controlling the downloads?

I'd suggest you repeat guided setup and if that changes anything.

Did Guided Setup several times and it fixed nothing. So I ran the clear program data and reconnected to load which it did after probably 8 hours.
So now I have program data for two weeks but...........I have the message "program data has run out" and the tivo search function gives a message that there's no data. It will record fine using manual recording or picking something off the directory on live tv.
Since I swapped hard drives, what can this possibly be? There must be a fix somewhere since it's not an uncommon problem.

It may be an issue with TiVo's servers not having guide data for your area. I'd suggest you call TiVo to see if it's a known problem.