maybe your hoster blocks the socket function? It’s required to receive the oembed protocol. If WP doesn’t receive the embed information it will just display the link (more about this oembed protocol here: http://wordpress.org/support/topic/cannot-get-video-to-embed-from-url ). I could reproduce the problem with a freehoster which also blocks socket connections.
Just wanted to update and let you know that this ended up being an issue on Youtube’s end. It randomly cleared itself up once it took its time registering the changes I made to the permissions on the video.