I was having the exact same problems. Then I began having authentification errors so RIM support had me uninstall Desktop 4.0 and install 3.6. We also experimented with changing profiles.
I ended up wiping the BBerry after all of that and it worked again. Sorry I cannot tell you which step actually did the fix. It is very troubling when the sync doesn't work reliably. Sometimes you don't notice something didn't sync until it is too late.