Some relevant IRC chatter:

(20:55:42) Saviq1: hi all, any idea why trying to sync to a playlist would ignore some 15% of the files?
(20:56:04) gabaug: Saviq1: either your device is full, or Banshee can't find the files on disk anymore
(20:56:11) gabaug: (most likely reasons)
(20:56:26) gabaug: I think the prior should be displayed in an Error source now though
(20:56:34) gabaug: if you're running >= 1.5.4
(20:56:34) Saviq1: no errors reported
(20:56:48) Saviq1: I'm on trunk / master / whatever it's called these days
(20:56:52) gabaug: is your device full?
(20:56:56) Saviq1: nope
(20:57:52) Saviq1: let me try and compare the two
(20:57:54) gabaug: have you tried running from a terminal w/ --debug to see if there's any relevant output?
(21:00:19) Saviq1: gabaug: yes, running in the console, no output at all when syncing
(21:01:16) gabaug: Saviq1: can you find one of the files that's not syncing in your library, and view its Properties, make sure file size > 0
(21:01:34) Saviq1: gabaug: yes, trying to compare the two now
(21:09:25) Saviq1: gabaug: ok, got one, it seems to ignore the whole album
(21:09:40) Saviq1: it's available, playable and all, but does not sync
(21:09:56) gabaug: Saviq1: maybe it needs to be transcoded for the device, but you have no appropriate encoder?
(21:10:09) Saviq1: nope, it's an mp3
(21:10:37) gabaug: Saviq1: if you manually manage the device and drag that song/album on, does it work?
(21:10:54) Saviq1: yes, just did it, and it's being transferred
(21:11:16) gabaug: hrm
(21:11:40) gabaug: Saviq1: this is a playlist in Music you're trying to sync from?
(21:11:44) Saviq1: I'll see if it gets removed upon sync now
(21:11:45) Saviq1: yes
(21:12:06) gabaug: Saviq1: is there anything weird about that album?  Does it have an Album Title set?
(21:12:15) Saviq1: yes, everything seems to be fine
(21:14:16) Saviq1: manual transfer does not seem to have changed the list of tracks in this source, trying to reread
(21:15:37) Saviq1: yup, it tries to remove them
(21:16:36) Saviq1: removed and readded to the playlist again, didn't change nothing
(21:16:50) gabaug: Saviq1: hrm...better file a bug

Seems it was caused by duplicate entries in the playlist...