Brian,
I'm building the package on a Windows 7 machine, and placing my msi packages in the Documents folder, and then burning them to disk. I then install the package on Windows XP machines straight from the disk.
On a side note, I did some more testing and these packages install just fine when I do the installation before joining the machine to our domain. So it appears something in our GPO is blocking access during installation. Does anyone know what files are being modified during the installation? If we can narrow it down I can give our GPO administrators somewhere to start looking in order to open up that access. I'm assuming that it has something to do with certs or tokens because like I said earlier, the password only version works just fine, even after joining to the domain.