Hi Martin,
Assuming you haven't any other Symantec products installed, try removing the Symantec folder from C:\Program Files, before trying to install NAV. Not being funny, but is it a genuine copy you are trying to install? I believe NAV 2004 has some sort of 'activation' procedure, similar to Windows XP, but I would have thought the error message would have been more specific, if that was the problem.