You probably heard by now that XNA Game Studio 3.1 is out.
After a quick download, uninstalling 3.0 and installing 3.1, I quickly put together this sample that shows how to use the new support for videos.
More info on the sample’s page, here.
Or, if you’re in a hurry, here’s the direct link to the download: VideoSample.zip