I believe I've seen that message is when the app is already installed, and is of the same version as the distribution. The installer is essentially saying that there's nothing it needs to do - nothing to add or remove.
You can force an install by changing the GUID associated with the distribution kit when you build it as I recall, even if everything else is unchanged.
If the app isn't really installed, maybe the distribution kit is improperly detecting that it is.
Menchar is correct that the message indicates that no software included in the distribution is of a higher version than what is already installed. You cannot (and should not) directly change the GUID for your installation, but instead you can (and should) increment the installer version. This is the version number on the first tab of the Edit Installer dialog.
Your customer can also check the Add/Remove Programs list to make sure the software isn't already installed. If they manually uninstall the previous version, their installer should run successfully. Note that this should not be necessary if the version numbers are properly incremented.
This software has not been installed before on the customer's computer. I have now solved the problem by changing the installer GUID (increasing the installer version made no difference). I can only assume that the original GUID was not as unique as I would have liked.