Just an update: After posting the above, I spent a bit more time playing with the plugin to make its layout "mesh" with my theme (Suffusion, one of the current top themes). It required one additional manual edit that you might consider making options:
First, suffusion uses the full text "(required") rather than an asterisk to indicate a required field, and as it uses a "label left" layout, the "(required) text comes AFTER the input field (rather than after the label). You can see any post on my site for an example (www.justin-klein.com). Thus, I had to edit the code to remove <span class="required">*</span> from $label_string, and add <span class="required">(required)</span> after $input_string.
You might consider making this a 3rd string which can be positioned either after $input_string or $label_string, enabling "edit-free" meshing with Suffusion or other themes which might mark "required" fields differently :)