Are you syncing files, contacts/appts, or avantgo-type things?
I frequently have this happen when my internet content may not be available...avantgo is notorious. :) If one of my channels is not available, I get a failure. Next time I sync, it works fine. Ditto with mobipocket.
Never had trouble with files, myself.
Here's a useful discussion of activesync and some of its failures, if you're still having trouble:
http://www.cewindows.net/faqs/t-shootactivesync.htm
Good luck!