I know this thread is a bit old now, but I had the same issue and found a solution that fixed my problem that no one else seems to have mentioned.
Basically I run my own wordpress server from home. I had a situation where I had a power outage and the wordpress server came back up BEFORE my dhcp server. Now linux is smart, it gave the same IP address, so everything should be working, right?
Sadly... DNS wasn't working.
So, my issue was that if the wordpress server cannot see youtube, then it will not embed the video. Once it has embedded the video once, it will stay embedded, which is why old posts work.
My guess is that wordpress needs to go to youtube to verify the clip and verify the sizes/settings on the clip in order to embed properly. It does this at the time you save your blog post. If the server cant see youtube, then the embed will always fail, no matter what tags you put around it.
Fix the servers access to youtube, click "update" on your posts affected, and the embed should start working again. :-)
Of course this is easier if you have access to your server... If you're in a hosting situation, I know some web hosts may not allow their servers direct internet access, or may have changed their policies which would mean embedding breaks. I guess a support call to your hosting provider is your only option in this instance. :-(