If your phone is jailbroken and you install a bunch of programs you will have that problem. The problem is caused by the partitioning of the internal drive space. There is a very large partition for installing music, videos, etc.. and a small partition that houses the operating system.
When the phone is jailbroken it opens the operating system partition and allows you to write to that space. When you install a program it puts it in the small partition. Over time you will start to get the out of space errors even though you have plenty of room on the music partition.
There is a work around for this problem and if you search this forum you will find discussions on it. Basically what the work around does is move the Applications folder over to the music partition and creates a dynamic link to where it used to be. So the system sees the Applications folder as being in the OS area but it is really just a shortcut to the new location.
If your phone is jailbroken, it's because you're running low on space where your third party apps reside. To fix this, you need to move your 3rd party apps to the media partition (where your music and videos are) and create a symlink. Just follow this guide: