Sending templatized e-mail to a million contacts
The big picture

First of all, consider the possibility that this is a trick question.  When sending bulk e-mail, the performance bottleneck is likely to be with the Mail Transfer Agent or the database query that fetches the contacts rather than with the text generation.  I would raise a concern with the interviewer that perhaps we should gather some evidence before making a premature effort to optimize the wrong part of the process.  Optimizing the code in this question (which takes about 2 seconds to run) will not make any noticeable difference to the time necessary to conduct the e-mail campaign.

Review

That said, if you had to optimize the text generation process, your changes would be a mild improvement.  The HashMap is more lightweight than the synchronized Hashtable, and the StringBuilder does save a bit of copying, though not by as much as you think, since you are still making four global substitution passes through the entire emailBody.

Strictly speaking, both the original code and your version of it are buggy.  Because string substitution is being done in multiple passes, it is possible that the output from one round of substitution could introduce a string that looks like a placeholder that ends up being inappropriately substituted in a subsequent round.  (Another example of this class of bug.)  Here, it's unlikely to be a problem unless someone decided to deliberately exploit the bug.

Alternative approach

If I really had to optimize this code, I would take a different approach entirely.  The same emailBody template is likely to used for a million emails.  Therefore, it would make sense to "pre-compile" the template…

Dear {{USER_NAME}},

According to our records, your phone number is {{USER_PHONE}} and 
your e-mail address is {{USER_EMAIL}}.  If this is incorrect, please 
go to {{LOGIN_URL}} and update your contact information.


… into code that looks like this:

public class C implements Template {
    public void write(Writer out, Map&lt;String, String&gt; params) throws IOException {
        out.write("Dear ");
        out.write(params.get("USER_NAME"));
        out.write("\n\nAccording to our records, your phone number is ");
        out.write(params.get("USER_PHONE"));
        out.write(" and \nyour e-mail address is ");
        out.write(params.get("USER_EMAIL"));
        out.write(".  If this is incorrect, please \ngo to ");
        out.write(params.get("LOGIN_URL"));
        out.write(" and update your contact information.\n");
        out.flush();
    }
}


The performance is likely to be unbeatable, since there is no longer any string substitution going on.  This is, in fact, very similar to the code that a JSP engine generates, and you could try to integrate a JSP implementation instead of reinventing the wheel.

As a bonus, you can stack layers of writers.  For example, you might pass it a subclass of FilterWriter that performs Format=Flowed line wrapping as per RFC 2646 to keep line lengths to a reasonable length as required by SMTP.  You could also stack that directly on top of a Writer that feeds the text directly to an SMTP socket.  Or, to obtain the resulting text as a string as in the original code, just use a StringWriter.

When I tried generating a million messages with a pre-compiled template, it completed the task in half the time of your code.  If you include the time to compile the template into executable form, it's still better than break-even for one million messages.  For a hundred million messages, it's about four times faster, compilation overhead included.