I've never seen this on my box. Even when full it should just delete the oldest show(s) to record the new one (unless you have every show set to save until I delete).
Have you tried scheduling another recording to see if it happens again?
If it does recur, the only suggestion is a cold reboot, then call Virgin if that doesn't fix it.
400Gb, Cachecard, EndPad, TiVoWeb etc and Sony VTX D800U STB
VirginMedia TiVo since 15th Feb 2011.