OK - his should really be in Linux. (admin - please move).
After searching the forums and seeing a lot of the same questions, I did some checking myself.
I had already set the video memory to 128MB, which should have been plenty but was limited to 1,024 x 768. But that was an improvement from 800 x 600. I checked my pcLinuxOS video settings and noted it was set to VESA not the nvidia driver.
Trying to set it to NV or nvidia failed.
In the end I set the video memory to the max. 256MB and reboooted and it came up fullscreen, finally.
I suppose this is a limitation of the guest operating system, having to use VESA instead of the NV or Nvidia drivers.
This should be spelt out as a lot of people are having linux guest screen resolution issues.