Well, that installation works fine, but that doesn't really prove anything, because the full installer is failing before it even gets that far.
Ok, we figured it out (we think.) For some reason, some of our user profiles on these servers have the User Environment variables set to %USERPROFILE%\Local_Settings\Temp instead of %USERPROFILE%\AppDateLocal\Temp. We have no idea why this is occurring, but we are fixing it now (although, whatever caused it may cause it to happen again.)