Hmm, so I can't find anything directly wrong with the code itself. Tested on a couple forums and working. If you are comfortable with PHP then you can try the following.
Around line 155 of scripts/verifyemail.inc.php is where things take place. Basically it's supposed to grab the uid and the key from the link in the email. It then does a lookup in the database and compares and md5 of a couple fields with the key from the email.
In your case, for some reason that's not matching. So if you know you're way around PHP you can maybe add a bit of code after the query to see if it's finding any results at all.
If you're not really comfortable debugging, then probably best to open up a support ticket so I can debug directly.
