Hmmm, it is starting to look like you might have to pay for this.

I have never used this plugin, so I can't give you a definitive answer, but looking at the link that you provided with, there is a subscription fee:

http://embed.ly/

It could be that early articles that I was reading (which suggested that it should just work) are now out of date.

Gary