OK, for those people suffering with this issue, here's the information you'll be interested in, and pretty much ignore the previous advice given in this thread by the so-called experts.
I got through to the department that handles the HR34s. They said this has become a known issue and they are in the middle of working on it. They say a new update will probably be sent anywhere between a few days to a week, but they are not sure. They also said deleting programs from your playlist will NOT fix the issue. He said people have cleared their entire playlist and were still at 0%! So no one should follow the advice given here by the so-called experts unless you wanna lose all your recordings without watching them first and still have nothing to show for it. And they said the Genie feature should not have taken up any additional hard drive space originally allocated to the user.
So again, don't delete recordings like mentioned here, don't buy new hard drives just because of this issue if you weren't planning on it beforehand, and never bend over for a company like some of the posters here enjoy doing. If you are paying for a service, make sure you get what you pay for!
I have a suggestion for you to try. It requires you deleting nothing, but should tell you if you did erase stuff if it would ever make an impact on the available %...
Go to your playlist, open up the options (yellow or dash buttons) and choose mark to delete. Then start selecting shows, and keep selecting them down your playlist. See if at any point the available % bar starts to show cross hatched on it. If it does, then if you where to actually delete that many shows, the cross hatched stuff should become available space. If you get to the point that you have everything in your playlist selected for deletion and you saw no cross hatching then deleting recordings will likely have zero affect..
Obviously, do not choose continue and confirm delete, unless you really want to erase what you have selected. You can just exit out leaving your playlist untouched. I don't know if you have ever used that function, but the cross hatch represents the amount that is selected to be erased, but the % number does not change unless you actually erase what you have selected.
I am simply suggesting this as a way to possibly verify what you where told by the csr you spoke to. If you see no cross hatching after selecting everything, then I'd say the csr is right on, if not, then I have to question their statements, because it would APPEAR erasing some programs would actually free up your hard drive. Just a thought....