Background: ClickOnce generates two files: The .application file - the "ClickOnce Application Deployment Manifest", and a setup.exe bootstrapper.
setup.exe will check for prerequisites, install any that are missing. When it's finished it will then run the .application file. The .application file will install and then run your application.
You can invoke the .application file directly, but then the prerequisites won't be installed.
Possible causes: Either you ran the .application file instead of setup.exe. Or the prerequisites specified in the bootstrapper are misconfigured.
How to fix: You can select which prerequisites are installed by opening the properties of your game project, selecting the Publish tab, and clicking "Prerequisites":

This will open a Prerequisites window, where you can select what redistributables will be installed by the bootstrapper.

For XNA, you need:
- Microsoft .NET Framework 4 Client Profile (x86 and x64)
- Microsoft XNA Framework Redistributable 4.0
- Windows Installer 3.1
These are automatically selected by the default Game Project template, so it should "just work".
The only other thought is that the computer you were installing on wasn't able to install XNA for some reason. Possibly it could not connect to Microsoft's website to get the installer. Although I would expect it to display an error during installation in this case. It is safe to run setup.exe repeatedly.