I wanted to revive this thread as I just ran into the same issue - a 64gb iPhone 5, suddenly showing as 30gb over capacity in iTunes, and failing to synch playlisits etc as a result. I did a full restore last weekend (NOT from the last backup but fully reinstalling the system, with music & apps reinstalled from iTunes, contacts email & notes relinked from iCloud). It worked once, but the next time I plugged it into the computer it was back at 12Gb over capacity... Which was irritating because it had taken HOURS to reset.
So I started playing with the check boxes under Options in the phone's Summary panel in iTunes. Unchecked 'Automatically synch when this iPhone is connected' and Checked 'Manually manage music and videos'. The only other option checked for my phone here is 'Synch only checked songs and videos'. Instantly the usage bar at the bottom of the page went back to the way I would expect it to be, with 20Gb of free space. So if you are having this issue, maybe it's worth a try.