First off, to quote my other answer, which may help you understand how this works:
Apps are stored on the /data partition, while the empty space you have is probably located on some other location, like internal SD card. Even if you have empty space elsewhere, apps couldn't be installed nowhere but on the /data partition.
(This may not apply to your case)
Do you have root on your device? If you have root, you can easily show the partition table to see what partitions have free space, and which do not.
Have you tried moving the applications to SD card (if possible)?
This option is located in Settings > Applications. Mind that most of the apps can't be transfered to SD card.