Late to the party, but I've not seen this anywhere else.
I originally did a clean install of 7.1. When I tried to upgrade it to 7.1.1 it bombed out with this error. I followed the method detailed in the post above and got a dodgy upgrade installed. Fast forward a few months and I wanted to upgrade to 7.1.4 but knew I'd have the same trouble, so... I went digging.
The original version is determined in libexec/zmsetup.pl getInstallStatus() called very early in the script . It parses /opt/zimbra/.install_history to determine the last package of zimbra-core that was successfully installed and configured. In my case all it contained was :
0000000000: INSTALL SESSION START
0000000000: INSTALLED 7.1.0_GA_3140.UBUNTU10_64
0000000000: INSTALL SESSION COMPLETE
0000000000: CONFIG SESSION START
0000000000: CONFIGURED BEGIN
0000000000: CONFIGURED END
0000000000: CONFIG SESSION COMPLETE
This meant the setup script was convinced I was doing an upgrade, but as it could not find a previous instance of zimbra-core it just had a "" version string.
I added :
0000000000: INSTALLED zimbra-core_7.1.0_GA_3140.UBUNTU10_64.deb
in the file directly above "INSTALL SESSION COMPLETE", and bob's yer mothers sisters husband.
I assume now there is some meaningful data in .install-history and all my databases are up to date that I'll not have this issue again.