I have several installs of wordpress on 2 different servers.
Both have cURL installed and curl test scripts work properly.
Both are shared hosting platforms (cpanel and virtualmin) with virtual hosts running PHP as user under fCGId.
php -m shows curl running as a php module
Auto-embed is enabled in Settings > media
I have cleared caches, turned off wp-cache or super cache, restarted apache after 2.9 upgrades, etc. to eliminate those as issues.
When I paste in a valid, embeddable Youtube or Vimeo URL, and save the post, the URL is saved as plain text and no auto-embed occurs.