Am in the process of upgrading site from Joomla 1.5 to Joomla 2.5. Installed new AllVideos 4.5.
Videos exist but keep getting the not found error.
Checked the media manager contents the videos are present.
This fails on my desktop (running xampp) and on my web host test site tc1.eibconsult.com/videos.html

This is identical to the existing Joomla 1.5 site as far a AllVideos is concerned.

1.
Please install Admin Tools from www.akeebabackup.com/ in order to fix your permissions as they should be and then reinstall the extension.

Right permissions on all joomla sites:
755 for folders
644 for files

2.
Check your path for the video file in AllVideos settings.