I took a look at the `paginate_links()` source code ([v3.5.1][1]) and there is this line ([#][2])

    $link = str_replace('%_%', 1 == $n ? '' : $format, $base);

that is giving you the empty string for the n=1 page. 

With your setup you have `$base = "%_%"` and `$format = "http://example.com/page/%#%/"` so this becomes:

    $link = str_replace('%_%', 1 == $n ? '' : "http://example.com/page/%#%/", "%_%");

where we have 2 cases:

    n=1:     $link = str_replace('%_%', '', "%_%");

    n>1:     $link = str_replace('%_%', "http://example.com/page/%#%/", "%_%");

and after the replace:

    n=1:     $link = '';

    n>1:     $link = "http://example.com/page/%#%/";


Here is an example of the output from `paginate_links()`:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href=''>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>

If you use instead ([#][3]): 

	'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
	'format' => '?paged=%#%',

then

    $link = str_replace('%_%', 1 == $n ? '' : "?paged=%#%", "http://example.com/page/%#%");	

and no replacement here, so  in both cases (n=1 and n>1)

    $link = "http://example.com/page/%#%";	

So you will get a non empty first page link and the the output of `paginate_links()` would be something like:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/1/'>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>

It looks like if the `$format` is any non-matching string in `$base` than it will give you non empty first page.

  [1]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1922
  [2]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1970
  [3]: http://codex.wordpress.org/Function_Reference/paginate_links#Examples