The problem mentioned below was the same as yours -
Sorted the problem.
I found a brandnew MS Publisher 2000 Upgrade on Ebay UK for £15.-
There are still a few more if anyone is interested.
For the upgrade to work, you don't need a previous version AFAIK, having any product from Office 97/2000 or newer will do.