You can fix this problem by converting the music files that the playlist. If you select them in iTunes and right click then select "Create AAC version" they will make a .m4a file which will sync across fine.
(I had the same problem as you and now it works. Some of my old MP3 files sync'd okay but some did not even though they were all the same file format. Anyway with Apple's format it always works.)
Creating new versions of files shouldn't be necessary.
Every song inside iTunes is represented by a unique ID. Playlists (when stored internally) are an ordered list of those IDs. If you export the playlist into a list of file locations at one computer, then import the list & files into another the IDs for each track will be different. On your new computer your iPhones list of IDs isn't matching the local library which, I suspect, is causing problems.
Delete the tracks by hand on the phone, then drag in the playlist again from iTunes.
The songs are not appearing on my iPhone so I can't delete them. (It is a new phone).
Based on what you said ad what worked for me I took another case of a file in a playlist not syncing and found that any change to the info of the file updates the file so that it then syncs correctly. Change anything from Artist, albulm, genre or number of track, doesn't matter, any change does the trick.
I have since found that changing the file format (although works) is not necessary. All you need to do is change any info of the file so that the song ID in Itunes gets recreated and it recognises it to sync it.
Change the artist name, or albulm name or anything on the info tab on the "Get info" option for each song.
Select all the songs you need to update and change a field, even if it is to put in a comment called "updated"
Much simpler than my first suggestion.