Most notebooks share the memory with the video card. Go in to the Bios and see how much memory is set to be shared with the video card.
It is some what unlikely that this is your issue so I am doing some further brain storming to see what I can figure out.
Also is this Windows XP home or Professional?
Some research I have done so far shows that this problem is being seen on PCs that had windows xp home and were then upgraded to xp professional.
Also check the task manager and in the bottom right hand corner it should show the commit Charge. if the second number shows something like 1024M Then even though system information is not showing correctly the PC is still utilizing the correct amount of memory.
If this is Windows XP Home, boot up in safe mode and log in as Administrator and see what windows xp shows for Ram. if it is showing 1 gig then It is either a profile issue or hardware/programs that are borrowing the ram and using it as its own making windows think you only have 256
These next few tips may not fix the problem but could help with PC performance:
Another thing to try is go to Windows explorer and navigate to the C:\winnt\prefetch folder and delete everything in there to make sure there is no corrupt files that can effect system and program startup. Then go to c:\winnt\temp and do the same thing there. There might be a couple of files in the temp directory that will not let you delete, if so just ignore those files. Reboot.
Also go to ccleaner.com and download the free ccleaner program (beware make sure to uncheck the yahoo toolbar install) nce you run the program, ignore the cleaner and go to the registry checker. Let it scan the registry and fix all problems, when prompted to make a back up click yes. Run this scan about 3 or four times because even after you fix the problems it may still find a few other issues. Reboot
Go to Start, click run and type msconfig.
Click on the SYSTEM.INI tab. Click on the + next to [386Enh]. Now click on [386Enh] and this should highlight it. Over on the right hand side click on the new button then type LocalLoadHigh=1 and now press enter. Now click the new button again and this time type DMABufferSize=64 and press enter. Now click on the services tab and look for Indexing Service. Uncheck Indexing Service, click ok and then restart your PC.
I would also check for spyware (if you haven't already) to make sure that isn't causing PC slowness.
Hopefully this information will help, and even if it doesn't help fix the 256 issue atleast be ale to speed the users PC back up.