Missing songs after 8.0 update and sync
Everything must first be on iTunes before it can be put on the iPhone. If the playlists and songs are not on iTunes on this new computer, it won't work, and syncing will only erase what you have on the iPhone, as it apparently has. 

In this case, all you can do to recover is:


Restore from a backup previous to trying to sync music to this new computer, recovering the previous, imperfect iPhone state, or 
Ideally, get the playlists and songs all loaded and working in iTunes first, then you can sync them to the iPhone.