Failed to embed

Hi.

Lately, WordPress starting to fail when I try to embed youtube links. Here’s what I get everytime.
http://screencast.com/t/suKdmQdkXKW

It posts only the link in text format, there’s no embeded youtube video.

I did a little research about this issue and found out that some plugins or themes used to cause it.
I don’t have any active plugins on my site and I tried 3 different themes, but the issue persists.

Does anyone have the idea what may be causing the issue and how to fix it?

Regards,
Ivica.