I've had no end of trouble with the new Library database under Vista when it comes to, well, everything actually... but specifically when dealing with Videos I have stored on my Network drive and on another computer - especially when using an Xbox 360 as an extender.
Well the steps I've used to make this work well are detailed in my post at my blog here:
http://www.shasam.net/archives/32
Hope it helps others.
Shane.