The iPhone has two partitions, a 300mb and the remaining x GB that the phone can spare.
Applications are installed to the 300mb partition, not allowing for many to be installed.
To free up some space, install BossTool to move the applications out of this partition.