I have AllVideos installed on a number of sites, both Joomla 2.5.8 and Joomla 3.2, and it works on all but one site.  The plugin is enabled on all sites, and the youtube link that I have tried unsuccessfully on the broken site I have copied identically to a number of other sites where it actually works.

Syntax is correct - {youtube}x8RrOiMHSg4|600|377{/youtube}

Here's the page where is doesn't work:

wilburg.dyndns.org/~test/index.php/computer/joomla-solutions/details/36/6/joomla-solutions-hidden-menus-and-menu-items.

Any ideas?

I get a forbidden error.

Are you sure that you are not blocking all requests as well? Is it working on a production enviroment?