Thanks for the tips. We thought everything was valid, but after another check, there were a few problems.
We've checked the path name to the js files - which are all fine, and the site is now XHTML compliant again.
Would this be the sort of error you would get if you tried to use the flyouts if the page hadn't fully loaded? Not that our site is that large, but the nav list is pretty large.
Threaded Mode