Not enough reputation to add this to taiken's answer sorry.
However wanted to add that his answer did work for me, however the links were in the 'localhost/date/2010' format. Whereas I needed 'localhost/postslug/2010' format. I was able to fix this by using a string replace on the output of wp_get_archives.
So depending on how your permalinks are set this code will fix the 404 problem and redirect the links to the custom post type permalink structure:
$yearly_archive = wp_get_archives(array( 'type' => 'yearly', 'post_type' => '<your post type name>', 'echo' => '0') );
$blog_url = get_bloginfo('url');
echo str_replace(($blog_url . '/date'), ($blog_url . '<your post type slug>'),$yearly_archive);