Welcome to AF!
It's probably referring to internal memory (different to the space left on the SD Card). If you head to Settings -> Applications -> Manage Applications -> Downloaded; you should see a list of installed apps. if you select an app, you'll have an option on that page to move to SD Card. That should free up some space on your phone to install apps.
Which model Galaxy is it? There are a few.