I had this problem at first, as well. For me, the fix was to keep WMP11 running on the host PC. Seems there is some underlying catalog that wasn't being updated until WMP11 was running. Never had this problem with WMC under Media Center. Not a big deal, though. I much prefer accessing video without having to launch Media Center on the 360.
I'm using WMC, not WMP11 (got the runtime codecs installed and use Media Player Classic for playback, WMP is just too much of a resource hog IMO), and its active in the background all the time to stream content, so that's not the problem. There's just some types of wmv files that won't show up. As for those that won't play, I'm pretty sure by now that's because of the codecs they use. The 360 doesn't seem to play .wmvs that use the MS mpeg4 condec. If I encode with regular WMV9 or WMV8, everything's fine.
I have spent the past days trying to find good and easy ways to convert my .avis to .wmv and I gotta say, it can be quite messy! I've tried almost a dozen tools that claim to do the job, yet none of them has all the features, flexibility or stability I am looking for. It's really quite frustrating.
Those than can batch-reencode often don't let me define custom settings for resolution and bitrate, others encode to wmv, but only with the mpeg4 codec (which, as I stated above, the 360 doesn't seem to play), some take hours to do a job that should only take 15 minutes, etc...
The chinese opensource project MediaCoder offers WMV support since a recent update, but its still touchy as hell and I haven't been able to get its wmv output working properly (if I get it to output a wmv at all, it only creates an empty container file 1/10th the size of the target). I had great hopes for GX::Transcoder, but its wmv conversion seems to be limited to a set of presets that override any custom settings I apply regarding resolution and compression rates. So far WinAVI seems like the easiest tool, though I'm not happ with the choice of quality options it offers me either, plus its not free. I'm open to suggestions...