jquery-ui-autocomplete is not loaded with wp_enqueue_script

Are you sure it is not loading? I tried this(using WordPress 3.6-beta1):

function add_scripts(){
  wp_enqueue_script( 'jquery-ui-autocomplete' );
}
add_action('wp_enqueue_scripts', 'add_scripts');

I got jQuery and jQuery migrate in the header:

<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/jquery.js?ver=1.9.1"></script> 
<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/jquery-migrate.js?ver=1.1.1"></script> 

And jQuery UI in the footer:

<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/ui/jquery.ui.core.min.js?ver=1.10.2"></script> 
<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/ui/jquery.ui.widget.min.js?ver=1.10.2"></script> 
<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/ui/jquery.ui.position.min.js?ver=1.10.2"></script> 
<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/ui/jquery.ui.menu.min.js?ver=1.10.2"></script> 
<script type="text/javascript" src="http://localhost/wordpress/wp-includes/js/jquery/ui/jquery.ui.autocomplete.min.js?ver=1.10.2"></script> 

Do you have wp_head() and wp_footer() in your theme? Have you tried it with a simple theme and all plugins deactivated?