The program that blew out the partition table and boot data wasn't Partition Magic, it was Symantec's Norton AntiVirus - and it did it again in another week (but I had all the details written down and fixed it in a couple minutes).
It appears NAV wakes up every week or so and looks at the boot info and partition table. It see's they're different from something it has stored somewhere and says, "EEEEEEEK! A Virus must have done this", and restores the old boot data and partition table.
Needless to say, I unistalled Norton and removed every trace of it I could find. Told the client he could reinstall it at his own risk.