Explanation in photo. I'm getting a little tired of having to restore again and again...
you click on your iPhone
and you are given sections in the middle. apps, movies, tv shows, etc etc
you need to select each tab and find out what is being synced to the phone to cause it to be overcapacity. perhaps you have selected all video or selected all songs checked. uncheck each category one by one until the capacity limit has been resolved. and then when you find the category that is causing this error you can tell iTunes to sync less stuff.
i don't think its a restore problem, if it was something to do with the phone you would see a lot of "other".
i can't tell from the picture if this is caused by "Other" data.
try clicking on manually manage music and video
if it is "other" then you need to back up the iPhone and set it up as "new"
another problem i have seen with a lot of "other" is iTunes match
you forget to delete your music in the iPhone and you click on turn on iTunes match. all your music gets thrown in "other" and it stays there until you turn off iTunes match and delete the music manually
your picture .. its just cropped too much. you should of posted the entire window.
from the looks of it i think your telling iTunes to sync your entire music or video collection