Dedupe Rule not working
Perhaps the best free explanation of CiviCRM's deduplication is from the CiviCRM blog last year (July 31, 2014): Understanding CiviCRM Dedupe Rules
For the whole process, I will let the author speak for themselves as it really is an excellent write up and worth reading in its entirety to understand the deduplication system.
For this question, I suspect the issue comes down to the usage of the rule.
Quoting the author of the blog post (from point 2):


Unsupervised rules are rules that are automatically checked when a user enters contact info into a form on the front end of the site (for example, when registering for an event, making a contribution, etc.). If a match is found, CiviCRM automatically merges the new contact into the old one, without checking with the user....

Supervised rules, on the other hand, are rules that are automatically checked when an admin or staff member enters info into the back end of the site (i.e., the admin interface). They do not automatically merge the contacts — they just trigger a pop-up suggesting that the contact may be a duplicate....

General rules are not triggered automatically at all. They can be run manually from the &quot;Find and Merge Duplicate Contacts&quot; page, or selected to run during a data import, but they do not ever just run on their own....



Rachel, based on your question, it looks as though your rule is setup correctly, but it is most likely set as a general rule, not the unsupervised rule for individuals. If you change the usage, I think you will find the results you're looking for.
Side note: for perhaps the best paid explanation, Civiteacher.com has excellent videos about CiviCRM deduplication.