MSI Installer errors 1013 & 11708

[Dave]

I have a customer running Windows 2000 Service Pack 4 that
is experiencing the following problem when attempting to
istall MSI packages:

The install fails immediately with the following pop-up
error:

Fatal Error
Installation ended prematurely because of an error

The followig 2 events are logged in the application log:

Source: MsiInstaller
Category: None
Event ID: 1013
Description:
=====================================================
Exception code: C0000005 ACCESS_VIOLATION
Module: C:\WINNT\System32\msi.dll
Function: 0x4e537e
=====================================================

Registers:
EAX:00000000 EBX:00000000 ECX:00000057 EDX:00000002
ESI:00087974 EDI:00416B68
CS:EIP:001B:004E537E SS:ESP:0023:0202FF2C EBP:0202FF78
DS:0023 ES:0023 FS:0038 GS:0000
Flags:00010246

Call stack:
Address Frame
004E537E 0202FF78 0
-- 0x00087974 0x00000000 0x00000200 0x0202FFEC
004E54B2 77E13578 0
-- 0x00000018 0xF08BC933 0x0F0C4D39 0x0000B885
A1645756 53EC8B55 0
-- 0x00000000 0x00000000 0x00000000 0x00000000

Source: MsiInstaller
Category: None
Event ID: 11708
Description:
Product (Product Name) - Instalation operation failed

I know the problem does not exist with the package,
because any package I try fails. I have tried
uninstalling SP4 back to SP3 and still get the same
results. Knowledgebase has nothing on either of the
errors or the cause of the failure.