FWIW, I was experiencing the same issue on a colleague's laptop.
Model: Dell Vostro 1500
OS: Vista Business 32-bit
MVT kept saying the issue was with outdated DATs, which I knew, and it was able to do the same as Security Center - kick off the update, however the VirusScan update kept getting to approx. 20-25% complete (I got this percentage by moving the mouse over the animated system tray icon every so often) and would restart at 0% a few times, before receiving the "An error occurred while updating" error message.
Reinstall at present isn't an option for me, as despite it being a legit copy (through Dell I'm assuming - it's a Dell laptop), I or my colleague don't have any paperwork regarding the McAfee registration.
I tried gorf's link - did a quick scan with MBAM, but it found nothing. A complete/thorough scan was taking too long, so I decided to stop it after an hour had passed.
The fix that worked for me was that suggested by bua_ako - running
http://download.mcafee.com/products/licensed/cust_support_patches/MSCPRXFIX.exe followed by a restart - despite not using a proxy to download updates.
Many thanks to those that have contributed.