You may also have a problem uploading because of the size of the vidoes. Check this tutorial.
www.ostraining.com/blog/joomla/media-man...d-size-in-joomla-25/ Or it could be a problem with maximum upload size. This will tell you how to deal with that by modifying your php.ini file.
www.ostraining.com/blog/joomla/installation-problems/ In Joomla 2.5 the stories folder is no longer needed. The media manager only accessed images/stories in 1.5, but in 2.5 you can place everything in the images folder. For All Videos, you do need to create an audio and videos folder and have the path correct in the configuration.
We do have a tutorial on using AllVideos, but you you might not need that at this point. Here is the link in case you want to review it.
www.ostraining.com/blog/joomla/using-allvideos-for-joomla/ If you can't get media manager to upload the files, you can always upload them to the correct location using an FTP client like Filezilla.
Let us know if that helps.
Cheers,
Ed