I've got a fully reproducible issue with signed installers. I've properly signed my installer using MSBuild tasks according to WiX documentation. I've then copied the installer to local disk on a virtual machine with fresh Vista SP2 installation. The VM has an Internet connection and it has been fully updated. When I run the installer and I get to the point of privilege elevation, I get "Unidentified Publisher" message.
The problem doesn't manifest when running the installer directly from network share. It doesn't happen when the installer is downloaded from Internet either. It also doesn't happen with plain MSI files. It's specific to Burn installers started from local disk that got to the machine without triggering separate certificate validation (e.g. via copy from network share).
Apparently Vista and Windows 7 install root certificates on-demand when they need to verify an application. Fresh Vista/7 contains next to no root certificates. Running from Internet or from network share triggers signature verification which in turn triggers download of the root certificate. There's no such verification when starting executables from local disk, which means it's up to Burn to trigger the root certificate download before running its embedded engine. Apparently Burn either doesn't trigger such verification or triggers it incorrectly. It somehow manages to run the embedded burn engine without triggering root certificate update. Burn engine is then reported as unsigned due to broken certificate chain.