I also have this problem. Feels to me like Xbox keeps it's own database of files being shared, WMP keeps it's own, and they've had a little falling out and don't talk near as much as they used to.
As someone mentioned, using "Add To Library" generally works, but sometimes not. I'm guessing it updates it's own database, but doesn't trigger Xbox to synch up.
Another thing you can do is play to video/audio file briefly in WMP, that way it's sure to get in the database.
Hopefully this little mess will be cleaned up at some point. The 360 has wanted to be The Media Hub since inception, and while for the first year or so it sure didn't act like it. Can't play AVI/DiVX? Helloo?
Doing much better now, but still some work to do.
(Oh, just wanted to add... if like me the only thing you use WMP for is to stream to the 360, do yourself a favor and remove all the watched directories in the library to save yourself some serious time when you're just trying to watch the new video yet have to sit and wait while it trudges through 24,900 media files to find the one you want to add.