Put up a patch here so you don't have to wait until the next update to fix this.
Unfortunately I do rely on the internal embed support of IPB 4, so if it's not processing the embeds properly, it doesn't give the Videos app anything to work with.
Have you tried using different urls to the same video?
Hmmm, full embed video or thumbnail? I honestly haven't looked into this yet. I'd be a little concern about it loading multiple embeds if a lot of new videos were posted at once.