Okay, I figured it out, thanks to Process Explorer!
I have a second, large hard drive that is mounted via a NTFS mount. It is also accessible via a drive letter. However, in trying to deal with issues with a completely different program, I had changed the TEMP env variable to point to the temp directory on this large hard drive via the NTFS mount. When I saw that specified on the msiexec command line via Process Explorer, I changed %TEMP% back to the user temp directory. When I tried the install this time, it worked fine.
So, if anyone else ever runs into this issue and their TEMP is not the usual place, have them make this change and it should work. I would not be surprised if it was an issue in msiexec and not your install package at all.
Stephen