@WebGuyMike: It's not that uncommon to have a "strong" password; what's more common is that people use the *same* strong password everywhere (thereby weakening it).
@smlunatick: I believe it IS a hardware issue...or rather: a firmware issue.
Now, for both of you--and mystified visitors--I have a potential solution (skip to the end of my post if you don't need to know what led to it).
On a DIR-625, I suddenly found myself locked out for months. Reinitializing the firmware was not a good option, since it sits on a corporate network and the technical support onsite...isn't...exactly. I figured someone had changed the password, and eventually we'd discover who did it, or someone would remember. In the interim, the DIR-625 reached "end of life" (sigh) and no later firmware was available (currently, 1.09)...so no clues or support options were forthcoming until a few minutes ago, when I started looking at the router's source code. On the login page, the password we enter is processed by a substr() command, which grabs the first 16 characters of what we type, and ignores the rest:
var goodp = document.myform.Password.value.substr(0,16);
Ok, fine; clearly my password is "cut off" at 16 characters before it's sent off to be validated. Now, having been a technician for 20 years, I know that techs make programming mistakes called "one-off" errors, especially when some programming tools start at 0, and others start at 1 (the code above starts at 0). So, I started trying variations of the last password I knew, + or -1 characters from that 16-character limit. After trying a few possible passwords, the router let me in at 15 characters of an expected password. Success!
Why? Well...once you're logged in, you can see the problem is in the source code for the page that accepts your new passwords:
<input type="password" id="password1" name="password1" maxlength="15" size="20" ....
The router strictly enforces an internal limit of 15 characters, but the front page's login accepts (unlimited, but prunes to) 16. Whoops! There may be yet another "1-off" issue in a password-padding loop immediately following the first code block (the substr), but I didn't really look into this.
The final recommendation comes down to this: whatever password you--or any visitors to this post--used: prune "what you think it should be" to no more than 15 characters and try again. If it works, your firmware contains the above-described bug..