I didn't read all 7 pages of the thread as many replies did not apply to me or seemed to not work for subsequent posters but I did solve the solution by trying a couple things and thought I'd add to the thread in case what worked for me might work for others. I apologize if this was already mentioned.
So, like many previous posters, I suddenly discovered that numerous albums I'd loaded onto my iPhone 4 had all but the first track of the album greyed out. While starting to read this thread, I began poking around in my phone and went to my largest playlist and began scrolling through it to see just how many albums were affected. It turned out to be most of those I'd added in my latest 2 update sessions so I figured it wouldn't be that many songs to edit manually. This is where I got the idea to simply manually delete all the greyed out songs and then just try again.
While I was deleting the greyed out songs, I also noticed a couple things:
1 - Every album that had been affected seemed to have 3 or 4 occurences of itself. By that I mean that I didn't have to just delete the album once but, rather, 3 or 4 times as it showed up more than once.
2 - A few of the unaffected albums (no songs greyed out) had also been added multiple times
So, not only did I delete every greyed out track but I also made a note of which albums had been added multiple times. Once I was done, I did a few things that may or may not have contributed to the successful fix but I just sort of intuitively did them just in case they may have helped. Not sure one way or the other.
First, I connected to my computer but immediately interrupted the attempted sync so I could go make a few changes to my music sync settings in iTunes. Here's what I did:
1 - I removed one of the smaller playlists of an artist who'd had some greyed out tracks. As soon as I did this, iTunes reacted strangely and said my selected sync songs were way over the size limit. It appeared to be recognizing the existing data on my phone as 'Other' and saw me trying to add a similar amount of new music. This is where I got the idea to do the next step
2 - I turned my phone off and then back on again while connected to iTunes so that it would sync as soon as the phone was turned on and (I hoped) would recognize the existing songs correctly rather than as 'Other'
So, long story short, iTunes then added about 125 tracks and they're now all fine and back to normal. I hope this helps at least a few of you.
Good luck & cheers!