It's possible that you haven't installed the System Restore Patch - without
which any current restore points are just space fillers.
To check this, look for the file C:\Windows\System\SMGR.DLL - r-click on the
file, and select Properties.
What's the version number? - if it's v4.90.0.3003 then you have installed
the patch, and we have to look elsewhere for the problem
if it's v4.90.0.2533, then you need to install the patch.

To install the patch, either visit Windows Update, or go here, and download
the patch for offline install
http://support.microsoft.com/default.aspx?scid=kb;en-us;Q290700
Run the installer, and windows should reset System Restore at the same time,
clearing your old restore points (which wouldn't have worked, anyhow), and
creating a single new one.
You should then reset the maximum allocation for SR by going to the
adjustment slider at System Properties | Performance | File System | Hard
Disk - most people find that 200-400MB is quite sufficient for most
purposes, unless installing/uninstalling large applications such as Office.