What version of AS are you using? You should be using AS 4.1, but you could try installing the AS 4.2 beta:
http://www.microsoft.com/windowsmobi...ivesync42.mspx
In what order did you load AS and WMP? (AS first, then WMP or WMP first, then AS) - The proper order should be WMP first, then AS. (The Setup program for ActiveSync 4.x installs updates for Windows Media Player 10. If Windows Media Player 10 is not installed, the Setup program does not install the updates).
The synching between these two packages is so closely intertwined that it is hard to know if this is a problem with ActiveSync or a problem with WMP.
Julie