Change the following lines at the bottom of the plugin to do Markdown _before_ WP-texturize (!= textile) and it should work.
add_filter(‘the_content’, ‘Markdown’, 6);
add_filter(‘the_excerpt’, ‘Markdown’, 6);
There is also a typo in _DoAnchors_reference_callback:
if ( isset( $g_titles[$link_id] ) ) {
(the ‘s’ in $g_titles has been forgotten.)