Synced iPhone to a new computer. iTunes cannot delete music from iPhone
I had the exact same issue when setting up a new computer—frustrating. What's happening is that iTunes sees that the current songs on the iPhone are taking up a lot of space, but iTunes is unable to figure out that many of the songs that are already on the iPhone are the same ones that are in your iTunes. Instead of syncronizing it to make all the songs match, it's saying there isn't enough space on the iPhone to add all of the songs in your iTunes library.

Based on a couple of posts I read on the web, I just tried this solution and it worked: 


Make sure you have all of your songs organized the way you want them in iTunes on your computer.
Connect your iPhone to your computer and sync your iPhone with iTunes, but on the music tab in iTunes, uncheck "sync music."  Set up all your other synchronization settings as you want them (Calendars, Contacts, Photos, Podcasts, etc). This way everything but your music will be correctly synched between your iTunes and iPhone. Once you have iTunes set to sync, click "Apply" in lover right corner of iTunes. This will sync everything except your music.
Next, you need to erase all of the songs on your iPhone. If there are any songs on your iPhone that aren't in your iTunes, you'll lose them, but that wasn't the case with me. To erase songs on iPhone, go to Settings → General → Usage → Manage Storage → Music → Edit (top right of screen). Click the red "-" to the left of "all songs" and tap delete.  Scary, but this will delete all songs on the iPhone itself.
Not sure if it's necessary but I restarted my iPhone after this.
Connect your iPhone to your computer.  Click on the little iPhone icon in the top left of the iTunes screen, and then click the Music tab in iTunes.  Put a check in the box by "Sync Music" and then select whether you want to sync your entire library or selected playlists, artists, etc.  Once you've selected what you want to sync, click on "Apply" in the bottom right corner of iTunes.


This will dump all of your iTunes songs/playlists back into your iPhone.