It seems when you download Apps onto an iPhone, the 'Other' section gets bigger. My total avail. space used to be 4.01 GB and then it went down to 3.93 GB, when I had only downloaded Apps. (And the App part is shown in green.)
Your iPhone must have info about each App... I did a restore and it seemed to clean up a bit though.