iPhone 3GS and iOS 5 don't sync
Have you tried removing all the songs from the device and just allowing a handful to sync?

Sometimes the tracking database gets in a bad state and cleaning things out lets you know it's safe to sync the whole load again.