I would start by asking if you are using a cache plugin? It is much more likely that would cause the problem with the nonce. Regardless of what the comment says in wp-includes/pluggable.php, a cursory review of the function's code would indicate that check_admin_referer (unless you are using an old version of WP) rarely would the referrer but focuses on if the nonce itself is valid (which if you are serving a cached version of the page probably is not). It only checks the referring page if there is no result from wp_verify_nonce, and since a non-cached page would have valid nonce, it would not check the referrer. See this post for more info.
Now, that being said, yes check_admin_referer wasn't the right choice for this location and while I'm not sure how that slipped by the beta testing phase, it has been changed twofold in 2.8.2 (which is currently available as a beta release, release candidate 4).
First, front-side nonces just use wp_verify_nonce to verify the nonce directly.
Second, front-side nonces are an optional feature defaulting to not being used. The reason for the addition of nonces was to combat form spam. But this is something that doesn't effect the entire universe of users, so rather than use it by default, it can be optionally used in 2.8.2+ by defining the constant WPMEM_USE_NONCE as equal to 1. Otherwise, no nonce (on the front-side).