Whoa, Whoa Whoa. When you get a low space warning, it should not be because of your ROM - I'm running CM7 with only 7.4 MB of free ROM space. IIRC, if you try to install a ROM that will not fit in ROM space it tells you right then and there that it cannot fir when you are installing.
The typical Low Memory warning that you receive when in the Android OS is one of the user space, not the ROM space. This will vary little between ROMs, but it is more so based on the number of apps you have installed. For example, if you have 100 apps installed under Pete's GB16, you still will have the same installed under another ROM.
As to why the message appeared after a backup, that depends - are you referring to n app backup (like Titanium Backup / MyBackupPRO) or to a full Nandroid backup (via your choice of recoveries)?
My guess is that when you installed the New ROM, something either got moved (from SDCard back to Usespace, which, technically, should not happen,) or that the ROM has an app in it's *system* space that you also have installed in user space, (Titanium Backup, ROM Manager, etc. are good candidates, as well as a few Google Apps) so that the ROM now thinks that those apps are in userspace whereas the previous ROM they were not.