I don't know if this changed anything, but before using apt-get I did log into the URL above and tried to download the games from OVI Store - this did start the app manager and did add the OVI repository.

I guess without this the apt-get would not have found the packages.

Earlier in this thread there are manual instructions for adding the OVI repository too.