Contact Sky, say you are thinking of leaving, and say it is because you cant record programs or use On Demand to download programs. They will probably offer you a new Sky box for free.
My brother had the same problem and rang Sky and they gave him a new Sky box for free.