Querystring parameter getting lost in rewrite rule

I think it’s probably your front end code that’s the problem.

Try this:

<?php
if( $letter = get_query_var( 'letter' ) ) 
{
        echo 'Current Letter: ' . $letter;
}
else
{
        echo 'Current Letter: All';
}