I've been having increasing problems with my Sky+ box over recent weeks culminating in programmes that would just hang during play back. I tried reinitialising the hard disk using the built-in firmware but this didn't solve the problem and I figured it was actually a hardware issue with the disk.
Today, I replaced the disk with one that has been sitting on a shelf for a while looking for a home. I have a Pace 3100 (second generation) Sky+ box which came with a 40GB Maxtor drive and I've replaced it with a 300GB Maxtor. While I apparently won't get all that space available to record on, I should expect a much increased capacity. Frankly, though, if it just recorded reliably with the same capacity I'd be happy.
There are a number of web sites that describe the process of replacing the disk and it's relatively straightforward. So far, touch wood, the new disk appears to be working fine and the few programmes I've tested certainly claim a much lower percentage for the disk space requirement.
The Pace Sky+ box requires a Torx T10 driver to remove the screws both for the case and for the hard drive brackets inside. The FAQ above points to Maplin and Screwfix Direct for this. I managed to get one from my local B&Q.