Warning, this will clear the contents of your Hard Disk!!
unplug the digibox from the mains power. Press and hold the 'left' and 'right' navigation buttons on the front of the digibox whilst you plug it back into the mains.
Continue holding the buttons in for about 20 seconds, and when the ring of light on the front comes on, press the 'select' button on the front of the digibox (between the left and right buttons you were holding).
The Sky+ recording logo lights will spin backwards and, according to the Sky engineer, this will "clear the hard drive".
Once this is done, unplug the digibox from the mains power again and this time press and hold the 'back up' button whilst you plug it back into the mains power.
Continue holding it for about 15 seconds until 3 lights on the front of the box come on and you get a full-screen message saying "Updating system software. Do not disconnect mains supply or satellite dish."
Leave the digibox doing its thing for about 10 minutes and it should be fixed! Try pausing and recording things again... hopefully you've just saved yourself £65 (price of an engineer callout).
If you've not been so lucky, call Sky but remember that if they try to charge you for an engineer callout, just ask to cancel your subscription and they should offer you a free callout to fix the problem - you're more valuable to them as a paying customer than the cost of an engineer callout.