There are, I think, three completely separate problems being discussed here.
1. Music only partially syncing (smarris)
Try deleting the music from the phone manually. I'm assuming here that you have it all safely backed up somewhere else, and that you realize that if this suggestion doesn't work it could leave you with no music on your phone.
Go to the Settings app, tap General --> Usage --> Music (you might have to wait a few seconds for that to show up). Then, for the "All Music" item, swipe to the left and tap "delete".
Then try syncing with iTunes again.
2. itunes losing the connection to the phone (thaipod).
Try turning your computer off, and turn the iphone off (hold the power button on the top for a few seconds, until you see the red "slide to power off"). Then turn everything on again, and try to sync with a USB cable, if that works try to sync via wifi.
3. Playlists not showing with "iCloud" (johnsanchez2022)
By "iCloud" do you mean iTunes Match? There's a discussion forum specifically for iTunes Match, and you're probably better off asking this question there. Playlists that contain "ineligible" tracks won't sync via iTunes Match, so that might be part of the problem, some "smart playlist" criteria won't work correctly at the moment, so that could be part of it.
I'm using a fifth-gen iPod Touch. I got the same 'could not be synced because the connection was lost' error. I found it occurred only when adding photos to the sync items. Using a different iPhoto library didn't help, nor did logging into a different account. So it wasn't a problem with any data at the user-level. I surmised an iPhoto or iTunes sync-related component went bad. I re-installed both. It must have replaced whatever wasn't working. Everything syncs correctly now.