The message indicates that the videos with problems have permissions that do not allow embedding in the third-party sites. You can't do anything about this as it's entirely controlled in YouTube. If you check directly in YouTube, you probably won't see any links to embed these videos in your site (since they are locked from embedding elsewhere).
In other words, it's not an AllVideos issue. It's a permissions issue related to specific YouTube videos you tested.
Fotis / JoomlaWorks Support Team
---
Please search the forum before posting a new topic :)